You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line contains one integer $n$ ($1 \le n \le 100$) — the length of string $s$.

The second line contains string $s$, consisting only of digits 0 and 1.

The third line contains $n$ integers $a_1, a_2, \dots a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the number of points for erasing the substring of length $i$.

Output

Print one integer — the maximum total points Vasya can get.

7
1101001
3 4 9 100 1 2 3

109

5
10101
3 10 15 15 15

23

Note

In the first example the optimal sequence of erasings is: 1101001 $\rightarrow$ 111001 $\rightarrow$ 11101 $\rightarrow$ 1111 $\rightarrow$ $\varnothing$.

In the second example the optimal sequence of erasings is: 10101 $\rightarrow$ 1001 $\rightarrow$ 11 $\rightarrow$ $\varnothing$.