CF1107E.Vasya and Binary String

Vasya has a string $s$ of length $n$ consisting only of digits 0 and 1. Also he has an array $a$ of length $n$.

Vasya performs the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue together the remaining parts (any of them can be empty). For example, if he erases substring 111 from string 111110 he will get the string 110. Vasya gets $a_x$ points for erasing substring of length $x$.

Vasya wants to maximize his total points, so help him with this!

瓦西娅有一个长度为 $n$ 的字符串 $s$，其中仅包含数字 0 和 1。此外，他还拥有一个长度为 $n$ 的数组 $a$。

瓦西娅重复执行以下操作，直到字符串变为空：选择一段由相同字符组成的连续子串，将其从字符串中删除，并将剩余部分（左右两部分）拼接起来（其中任一部分都可能为空）。例如，若他从字符串 111110 中删除子串 111，则得到字符串 110。删除长度为 $x$ 的子串可获得 $a_x$ 分。

瓦西娅希望使总得分最大化，请你帮助他实现这一目标！

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$.

第一行包含一个整数 $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$ 的子串所获得的分数。

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

输出一个整数——Vasya 能获得的最高总分。

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$.

在第一个例子中，最优的擦除序列为：1101001 $\rightarrow$ 111001 $\rightarrow$ 11101 $\rightarrow$ 1111 $\rightarrow$ $\varnothing$。

在第二个例子中，最优的擦除序列为：10101 $\rightarrow$ 1001 $\rightarrow$ 11 $\rightarrow$ $\varnothing$。