У Васи есть строка \(s\) длины \(n\) состоящая только из цифр 0 и 1. Так же у него есть массив \(a\) длины \(n\).
Вася выполняет следующую операцию до тех пор пока строка не станет пустой: взять последовательный подотрезок одинаковых символов, удалить его из строки и склеить оставшиеся две части (любая из оставшихся частей может быть пустой). Например, если Вася удалит подстроку 111 из строки 111110 он получит строку 110. За удаление строки длины \(x\) Вася получает \(a_x\) очков.
Вася хочет максимизировать суммарное количество очков, помогите ему с этим!
Выходные данные
В единственной строке выведите число — максимальное количество очков которое может получить Вася.
Примечание
В первом тестовом примере оптимальная последовательность удалений имеет следующий вид: 1101001 \(\rightarrow\) 111001 \(\rightarrow\) 11101 \(\rightarrow\) 1111 \(\rightarrow\) \(\varnothing\).
Во втором тестовом примере оптимальная последовательность удалений имеет следующий вид: 10101 \(\rightarrow\) 1001 \(\rightarrow\) 11 \(\rightarrow\) \(\varnothing\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1101001
3 4 9 100 1 2 3
|
109
|
|
2
|
5
10101
3 10 15 15 15
|
23
|