【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$,含义如题面所示。

输出格式


一行,为最少的成本。

输入输出样例

输入样例 #1

2 1 2
1 1
2

输出样例 #1

0

输入样例 #2

6 2 3
1 1 2 2 1 2
2
2

输出样例 #2

6

输入样例 #3

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

输出样例 #3

343542

输入样例 #4

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

输出样例 #4

20172

输入样例 #5

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

输出样例 #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$。 温馨提示:请注意时限。