Список изменений:
Благодарим вас за непрерывную поддержку игры!
И это все? С небольшим разочарованием вы запускаете игру и нажимаете на новый режим. Написано «Цветные платформы».
В ряд расположены $$$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
