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