Algebra Flash

题意翻译

小 A 在电脑上玩跳格子游戏，该游戏一共有标号 $1$ ~ $n$ 的格子，每个格子都有一个颜色 $c_i$。小 A 需要控制跳跳龙从 $1$号格子跳到 $n$ 号格子，每次只能往前跳 $1$ 个或 $2$ 个格子。初始时所有格子都未激活（包括 $1$ 和 $n$），处于未激活的格子游戏会直接失败。但是花费 $x_k$ 金币可以激活所有颜色为 $k$ 的格子。所以游戏前，你需要预定一个购买颜色方案，使得对应颜色的格子在游戏开始前就被激活，以便你能控制跳跳龙到达终点。小 A 希望花费最少的金币完成任务，请求出最小花费。

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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

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

**题意翻译**

小 A 在电脑上玩跳格子游戏，该游戏一共有标号 $1$ ~ $n$ 的格子，每个格子都有一个颜色 $c_i$。小 A 需要控制跳跳龙从 $1$号格子跳到 $n$ 号格子，每次只能往前跳 $1$ 个或 $2$ 个格子。初始时所有格子都未激活（包括 $1$ 和 $n$），处于未激活的格子游戏会直接失败。但是花费 $x_k$ 金币可以激活所有颜色为 $k$ 的格子。所以游戏前，你需要预定一个购买颜色方案，使得对应颜色的格子在游戏开始前就被激活，以便你能控制跳跳龙到达终点。小 A 希望花费最少的金币完成任务，请求出最小花费。

**题目描述**

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?

**输入输出格式**

**输入格式**

第一行包含两个整数 $ 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
```**题意翻译** 小 A 在电脑上玩跳格子游戏，该游戏一共有标号 $1$ ~ $n$ 的格子，每个格子都有一个颜色 $c_i$。小 A 需要控制跳跳龙从 $1$号格子跳到 $n$ 号格子，每次只能往前跳 $1$ 个或 $2$ 个格子。初始时所有格子都未激活（包括 $1$ 和 $n$），处于未激活的格子游戏会直接失败。但是花费 $x_k$ 金币可以激活所有颜色为 $k$ 的格子。所以游戏前，你需要预定一个购买颜色方案，使得对应颜色的格子在游戏开始前就被激活，以便你能控制跳跳龙到达终点。小 A 希望花费最少的金币完成任务，请求出最小花费。 **题目描述** 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? **输入输出格式** **输入格式** 第一行包含两个整数 $ 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 ```