呃,是吗?有点失望,你启动游戏并单击新的游戏模式。它说“彩色平台”。
有$$$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