E. Вася и двоичная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть строка $$$s$$$ длины $$$n$$$ состоящая только из цифр 0 и 1. Так же у него есть массив $$$a$$$ длины $$$n$$$.

Вася выполняет следующую операцию до тех пор пока строка не станет пустой: взять последовательный подотрезок одинаковых символов, удалить его из строки и склеить оставшиеся две части (любая из оставшихся частей может быть пустой). Например, если Вася удалит подстроку 111 из строки 111110 он получит строку 110. За удаление строки длины $$$x$$$ Вася получает $$$a_x$$$ очков.

Вася хочет максимизировать суммарное количество очков, помогите ему с этим!

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

Первая строка содержит число $$$n$$$ ($$$1 \le n \le 100$$$) — длину строки $$$s$$$.

Вторая строка содержит строку $$$s$$$, состоящую только из цифр 0 и1.

Третья строка содержит $$$n$$$ чисел $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ равно количеству очков за удаление подстроки длины $$$i$$$.

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

В единственной строке выведите число — максимальное количество очков которое может получить Вася.

Примеры
Входные данные
7
1101001
3 4 9 100 1 2 3
Выходные данные
109
Входные данные
5
10101
3 10 15 15 15
Выходные данные
23
Примечание

В первом тестовом примере оптимальная последовательность удалений имеет следующий вид: 1101001 $$$\rightarrow$$$ 111001 $$$\rightarrow$$$ 11101 $$$\rightarrow$$$ 1111 $$$\rightarrow$$$ $$$\varnothing$$$.

Во втором тестовом примере оптимальная последовательность удалений имеет следующий вид: 10101 $$$\rightarrow$$$ 1001 $$$\rightarrow$$$ 11 $$$\rightarrow$$$ $$$\varnothing$$$.