CF1767E.Algebra Flash

Algebra Flash 2.2 has just been released!

Changelog:

• New gamemode!

Thank you for the continued support of the game!

Huh, is that it? Slightly disappointed, you boot up the game and click on the new gamemode. It says "Colored platforms".

There are $n$ platforms, numbered from $1$ to $n$, placed one after another. There are $m$ colors available in the game, numbered from $1$ to $m$. The $i$-th platform is colored $c_i$.

You start on the platform $1$ and want to reach platform $n$. In one move, you can jump from some platform $i$ to platforms $i + 1$ or $i + 2$.

All platforms are initially deactivated (including platforms $1$ and $n$). For each color $j$, you can pay $x_j$ coins to activate all platforms of that color.

You want to activate some platforms so that you could start on an activated platform $1$, jump through some activated platforms and reach an activated platform $n$.

What's the smallest amount of coins you can spend to achieve that?

代数速算 2.2 版本刚刚发布！

更新日志：

• 新增游戏模式！

感谢大家对本游戏的持续支持！

嗯？就这些？你略感失望，但还是启动了游戏，并点击进入新游戏模式。屏幕上显示：“彩色平台”。

共有 $n$ 个平台，编号从 $1$ 到 $n$，依次排列。游戏中共有 $m$ 种颜色，编号从 $1$ 到 $m$。第 $i$ 个平台的颜色为 $c_i$。

你起始于平台 $1$，目标是到达平台 $n$。每次移动，你可以从某个平台 $i$ 跳到平台 $i + 1$ 或 $i + 2$。

所有平台初始均处于未激活状态（包括平台 $1$ 和平台 $n$）。对于每种颜色 $j$，你可以花费 $x_j$ 枚金币来激活所有该颜色的平台。

你需要激活若干平台，使得你能从已激活的平台 $1$ 出发，经过一系列已激活的平台跳跃，最终抵达已激活的平台 $n$。

请问：达成上述目标所需的最少金币数量是多少？

The first line contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$; $1 \le m \le 40$) — the number of platforms and the number of colors, respectively.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le m$) — the colors of the platforms.

The third line contains $m$ integers $x_1, x_2, \dots, x_m$ ($1 \le x_i \le 10^7$) — the cost of activating all platforms of each color.

第一行包含两个整数 $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$），表示激活每种颜色的所有平台所需的费用。

Print the smallest amount of coins you can spend to activate some platforms so that you could start on an activated platform $1$, jump through some activated platforms and reach an activated platform $n$.

输出激活若干平台所需的最少硬币数量，使得你可以从已激活的平台 $1$ 出发，经过若干已激活的平台跳跃，最终到达已激活的平台 $n$。