← 返回题目列表

Codeforces · 1767/E

E. 代数闪存

中文机器翻译题面 查看原题

呃,是吗?有点失望,你启动游戏并单击新的游戏模式。它说“彩色平台”。

有$$$n$$$个平台,编号从$$$1$$$到$$$n$$$,依次放置。游戏中有 $$$m$$$ 颜色可供选择,编号从 $$$1$$$ 到 $$$m$$$。第 $$$i$$$ 平台的颜色为 $$$c_i$$$。

您从平台 $$$1$$$ 开始,想要到达平台 $$$n$$$。您可以一步从某个平台 $$$i$$$ 跳转到平台 $$$i + 1$$$ 或 $$$i + 2$$$。

所有平台最初均已停用(包括平台 $$$1$$$ 和 $$$n$$$)。对于每种颜色 $$$j$$$,您可以支付 $$$x_j$$$ 硬币来激活该颜色的所有平台。

您想要激活一些平台,以便您可以从激活的平台 $$$1$$$ 开始,跳过一些激活的平台并到达激活的平台 $$$n$$$。

要实现这一目标,您至少可以花费多少金币?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le m \le 40$$$) — 分别是平台数量和颜色数量。

第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le m$$$) — 平台的颜色。

第三行包含 $$$m$$$ 整数 $$$x_1, x_2, \dots, x_m$$$ ($$$1 \le x_i \le 10^7$$$) — 激活每种颜色的所有平台的成本。

输出

打印您可以花费的最小数量的硬币来激活一些平台,这样您就可以从激活的平台$$$1$$$开始,跳过一些激活的平台并到达激活的平台$$$n$$$。

示例

输入 #1

5 3
1 3 2 3 1
1 10 100

输出 #1

11

输入 #2

5 3
1 3 2 3 1
1 200 20

输出 #2

21

输入 #3

4 2
2 2 1 1
5 5

输出 #3

10

输入#4

10 10
3 8 6 2 10 5 2 3 7 3
9 7 4 2 1 8 2 6 2 2

输出#4

15