← 返回题目列表

Codeforces · 1107/E

E. Vasya 和二进制字符串

中文机器翻译题面 查看原题

Vasya 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含数字 0 和 1。他还有一个长度为 $$$n$$$ 的数组 $$$a$$$。

Vasya 执行以下操作,直到字符串变空:选择一些连续的相同字符的子字符串,将其从字符串中删除,并将剩余部分粘合在一起(其中任何部分都可以为空)。例如,如果他从字符串 111110 中删除子字符串 111,他将得到字符串 110。 Vasya 因删除长度为 $$$x$$$ 的子字符串而获得 $$$a_x$$$ 分。

Vasya 想要最大化他的总积分,所以帮助他吧!

输入

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

输出

打印一个整数 — Vasya 可以获得的最大总分。

示例

输入 #1

7
1101001
3 4 9 100 1 2 3

输出 #1

109

输入 #2

5
10101
3 10 15 15 15

输出 #2

23

注意

在第一个示例中,最佳擦除顺序是: 1101001 $$$\rightarrow$$$ 111001 $$$\rightarrow$$$ 11101 $$$\rightarrow$$$ 1111 $$$\rightarrow$$$ $$$\varnothing$$$。

在第二个示例中,最佳擦除顺序是: 10101 $$$\rightarrow$$$ 1001 $$$\rightarrow$$$ 11 $$$\rightarrow$$$ $$$\varnothing$$$。