E. Algebra Flash
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Выпущена новая версия: Algebra Flash 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$$$.

Какое наименьшее количество монет потребуется для достижения этого?

Входные данные

В первой строке записаны два целых числа $$$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$$$.

Примеры
Входные данные
5 3
1 3 2 3 1
1 10 100
Выходные данные
11
Входные данные
5 3
1 3 2 3 1
1 200 20
Выходные данные
21
Входные данные
4 2
2 2 1 1
5 5
Выходные данные
10
Входные данные
10 10
3 8 6 2 10 5 2 3 7 3
9 7 4 2 1 8 2 6 2 2
Выходные данные
15