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?

Input

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.

Output

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$.

见题面 Input 部分

见题面 Output 部分