T143361 【AHAOI Round1 pj T3】祖玛

xrk 大神在玩一个游戏祖玛，因为他觉得游戏中的珠子有一种高雅的美。

祖玛的规则是这样的：有一串有着不同颜色的珠子，我们可以在两个珠子之间插入一个珠子，或整串珠子的结尾处（**注意不能是开头**）尾随一个珠子。如果在任意时刻，有一段连续且长度**不小于** $k$ 的同色珠子，那么这段连续的同色珠子就可以消失，两端的珠子会因此合并（如果有的话）。注意，**合并后可能又会形成一段这样的珠子，也能以同样的方式消失，以此类推**。 xrk 大神觉得各种各样的限制很烦，因此破解了游戏：**他可以随时射任意颜色的珠子，并且可以控制珠子的消失**（也就是在一个时刻，有一段连续且长度不小于 $k$ 的同色珠子，他**可以选择让这段消失或不消失**）。但为了让这个游戏继续高雅，他决定增加一条限制：**发射一个颜色为 $i$ 的珠子，有 $w_i$ 的代价**。 现在有一段长度为 $n$ 的珠子串，请你告诉 xrk 能使得**整串珠子消失的最小总代价**。

无

无

样例 #1 相关：可以看到初始给定的珠子串也有可能直接满足了消失条件。 样例 #2 解释： 在第 $3$ 个珠子和第 $4$ 个珠子间射 $1$ 个颜色为 $2$ 的珠子后： 1 1 2 2 1 2 ↓ 1 1 2 2 2 1 2 ↓ 1 1 ~~2 2 2~~ 1 2 ↓ 1 1 1 2 ↓ ~~1 1 1~~ 2 ↓ 2 此时还需要再尾随 $2$ 个颜色为 $2$ 的珠子，使得剩下的这个珠子消失。总共发射了 $3$ 个颜色为 $2$ 的珠子，代价为 $3 \times w_2 = 3 \times 2 = 6$。可以证明没有更小的代价。 样例 #3 和 样例 #4 相关：可以看到完全相同的珠子串，随着代价的改变，最优的射珠子方案也会有所改变。 样例 #5 相关：可以看到 xrk 的控制珠子消失的能力：此时有两段连续的 `1 1` 段，他可以选择不让第一段 `1 1` 消失而是让第二段消失，从而使得 `1 1 2 1 1 2 1 2 -> 1 1 2 2 1 2 -> 1 1 1 2 -> 2`，此时再尾随一个颜色为 $2$ 的珠子即可。可以发现如果他没有控制消失的能力，需要花费的最小代价会更高。