У Васи есть строка \(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\).
В единственной строке выведите число — максимальное количество очков которое может получить Вася.
В первом тестовом примере оптимальная последовательность удалений имеет следующий вид: 1101001 \(\rightarrow\) 111001 \(\rightarrow\) 11101 \(\rightarrow\) 1111 \(\rightarrow\) \(\varnothing\).
Во втором тестовом примере оптимальная последовательность удалений имеет следующий вид: 10101 \(\rightarrow\) 1001 \(\rightarrow\) 11 \(\rightarrow\) \(\varnothing\).
7 1101001 3 4 9 100 1 2 3
109
5 10101 3 10 15 15 15
23
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач