字符串划分

题目描述

Y 同学手中有一个由 $N$ 个小写英文字母组成的字符串 $S$。

他希望将这个字符串划分为若干个连续的子串 $T_1, T_2, \ldots, T_k$，使得原字符串 $S = T_1 + T_2 + \cdots + T_k$（即这些子串按顺序拼接后等于原串）。

为了保证划分的质量，Y 同学要求每一个子串都必须满足无重复字符的条件，即子串中的每个字母至多出现一次。

此外，Y 同学还制定了一套价值评估标准：如果一个子串的长度为 $L$，那么它将贡献 $a_L$ 的价值。划分方案的总价值定义为所有子串价值之和。

请你帮助 Y 同学寻找一种划分方案，使得最终得到的总价值最大。

输入格式

第一行包含一个正整数 $N$，表示字符串的长度。 第二行包含一个长度为 $N$ 的仅包含小写字母的字符串 $S$。 第三行包含 $N$ 个正整数 $a_1, a_2, \ldots, a_N$，其中 $a_i$ 表示长度为 $i$ 的子串所对应的价值。

输出格式

输出一行一个整数，表示能够获得的最大价值之和。

样例

样例输入 #1

6
street
2 1 7 4 3 3

样例输出 #1

13

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 10^5$， $1 \le a_i \le 10^9$。