Statement is not available in English language
E. Крош и строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кроша есть бинарная строка $$$s$$$ длины $$$n$$$, состоящая из $$$n$$$ символов $$$0$$$ и $$$1$$$. За один ход Крош может взять два различных соседних символа $$$s_i$$$ и $$$s_{i + 1}$$$ и заменить один из них на другой. Цена такой замены равна $$$c_i$$$. Например, если $$$s_i = 0$$$, $$$s_{i + 1} = 1$$$, то вы можете за $$$c_i$$$ заменить либо $$$0$$$ на $$$1$$$, либо $$$1$$$ на $$$0$$$. Найдите минимальную суммарную стоимость замен, с помощью которых можно получить строку, состоящую из всех единиц.

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

Вам дано число $$$1 \le n \le 10^5$$$ – длина строки. В следующей строке входных данных вам задана строка $$$s$$$ из $$$n$$$ символов $$$0$$$ и $$$1$$$. Гарантируется, что в строке есть хотя бы одна единица. В следующей строке вам заданы $$$n - 1$$$ число – стоимости замен $$$0 \le c_i \le 10^9$$$. $$$n$$$-е число не задано, так как для последнего символа не существует соседнего справа.

Система оценки
  • Подзадача 1 (15 баллов): для любого $$$1 \le n \le 10$$$;
  • Подзадача 2 (15 баллов): для любого $$$1 \le i \le n - 1$$$ $$$s_i \neq s_{i + 1}$$$, необходимые подзадачи – нет.
  • Подзадача 3 (15 баллов): для всех $$$1 \le i \le n$$$ $$$c_i = 1$$$
  • Подзадача 4 (55 баллов): без дополнительных ограничений, необходимые подзадачи – 1, 2, 3.
Выходные данные

Выведите ответ на задачу.

Пример
Входные данные
5
10010
2 4 1 3
Выходные данные
6