【AHAOI Round1 pj T3】巧克力机器

xlz是一个制作巧克力的大师。~~xlz秘制~~巧克力~~既实惠又管饱~~非常好吃，每天都有好几个顾客去她家买巧克力，并五星好评~~分期付款~~。可是xlz嫌人工做巧克力有点麻烦，而她的手最近因为老玩钢琴块而总是酸痛，于是~~一名外国小哥~~dbxxx帮xlz制作了一台巧克力机，可以自动制作巧克力。可是第一天，她就遇到了一些麻烦。

xlz制作的巧克力是板状的，可以看做一个宽度为1的长方形。巧克力机有一个巧克力滑道，可以看做一个宽度为1，长度无限的长方形。 为方便表述我们作如下定义： 巧克力块：定义为一个 $1 \times 1$ 尺寸的巧克力，属于巧克力基本单位；一个巧克力块有属于自己的类别。总共有 $m$ 种类别，记为 $1 \sim m$。 巧克力块序列：若干巧克力块组成的连续序列。 巧克力：属于巧克力块序列，且满足以下条件： - 该巧克力块序列长度 $\ge k$；（k为读入内容） - 组成该巧克力块序列的每个巧克力块的种类相同。 初始状态下，在滑道上有一个长度为 $n$ 的巧克力块序列。巧克力机有以下操作： - **加入操作**：在一个巧克力块的**右侧**插入一个巧克力块。 > 比如： `1 2` 之间可以插入一个`3`类巧克力块：`1 3 2`。也可以在这段末尾放下：`1 2 3`。但注意不可以是 `3 1 2`！ - **取出巧克力操作**：取出一块巧克力。取出巧克力后，如果原巧克力两端左右都有巧克力块序列，那么巧克力机将通过传送带传动将它们合并。 > 比如：**k = 3**，对于`2 2 1 1 1 2 2 3`，可以把`1 1 1`这块巧克力取出，两端合在一起：`2 2 2 2 3`，再可以把`2 2 2 2`这块巧克力取出。经过两次取出巧克力操作后，将只剩下一个`3`类巧克力块。 （提示：如果想把这个 `3` 类巧克力块移除，可以再添加 `2` 个 `3` 类巧克力块，然后一并移除它们。） 每一类巧克力块的成本都不同，一个 $i$ 类的巧克力块的成本是 $w_i$ 元，而取出巧克力操作无成本。 勤俭节约的xlz为省钱，想知道怎么通过最少的成本添加巧克力块，以清空巧克力滑道。

第一行三个整数 $n,m,k$，含义如题面所示。 第二行为空格隔开的 $n$ 个整数，描述了初始机器滑道上的巧克力块序列。第 $i$ 个整数 $a_i$ 表示第 $i$ 格的巧克力块为 $a_i$ 类巧克力。 第三行为空格隔开的 $m$ 个整数，表示 $w_i$，含义如题面所示。

一行，为最少的成本。

2 1 2
1 1
2

0

6 2 3
1 1 2 2 1 2
2
2

6

7 2 3
1 1 2 2 1 2 2
114514
1919810

343542

7 2 3
1 1 2 2 1 2 2
114514
10086

20172

10 5 5
1 4 3 2 1 4 5 3 3 2
1
2
3
4
5

77

此处解释第2个样例。 在第 $3$ 个巧克力块右侧插入一个 $2$ 类巧克力块。此时的机器滑道： `1 1 2 2 2 1 2` 将 $[3, 5]$ 这块巧克力拿走，两边合一起： `1 1` ~~`2 2 2`~~ `1 2` ↓ `1 1 1 2` 将 $[1, 3]$ 这块巧克力拿走： ~~`1 1 1`~~ `2` ↓ `2` 在后边补 $2$ 个 $2$ 类巧克力块（进行两次插入操作）。此时机器滑道变成： `2 2 2` 将 $[1, 3]$ 这块巧克力拿走，巧克力滑道为空。 总共添加了 $3$ 个 $2$ 类巧克力块，成本为 $2 \times 3 = 6$ 元。 可以证明 $6$ 元是最小的成本。 ---- **本题采用subtask。** 对于 $10\%$ 的数据，$m = 1$。 对于 $30\%$ 的数据，$m \le n \le 10$，$k \le 2$。 对于另外 $20\%$ 的数据，$m = 2$。 对于 $100\%$ 的数据，$1 \le m \le n \le 100$，$k \le 5$。 温馨提示：请注意时限。