#2202. [GESP202406 六级] 计算得分

[GESP202406 六级] 计算得分

Description

小杨想要计算由 mm 个小写字母组成的字符串的得分。

小杨设置了一个包含 nn 个正整数的计分序列 A=[a1,a2,...,an]A=[a_1,a_2,...,a_n] ,如果字符串的一个子串由 k(1kn)k(1 \leq k \leq n) 个 abc 首尾相接组成,那么能够得到分数 ,并且字符串包含的字符不能够重复计算得分,整个字符串的得分是计分子串的总和。

例如,假设 n=3n=3 ,字符串 dabcabcabcabzabc 的所有可能计分方式如下:

- d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc,其中 d 和 abz 不计算得分,总得分为 a1+a2+a1a_1 + a_2 + a_1 - d+abc+abc+abc+abz+abc,总得分为 a1+a1+a1+a1a_1 + a_1 + a_1 + a_1 - d+abcabcabc+abz+abc,总得分为 a3+a1a_3 + a_1

小杨想知道对于给定的字符串,最大总得分是多少。

Input Format

第一行包含一个正整数 nn ,代表计分序列 AA 的长度。

第二行包含 nn 个正整数,代表计分序列 AA

第三行包含一个正整数 mm ,代表字符串的长度。

第四行包含一个由 mm 个小写字母组成的字符串。

Output Format

输出一个整数,代表给定字符串的最大总得分。

3
3 1 2
13
dabcabcabcabz

9

Hint

样例解释

最优的计分方式为 d+abc+abc+abc+abz,总得分为 a1+a1+a1a_1 + a_1 + a_1,共 99 分。

数据范围

子任务编号 数据点占比 nn mm aia_i 特殊条件
1 20%20\% 20\leq 20 105\leq 10^5 1000\leq 1000 对于所有的 i(1in)i(1\leq i\leq n) , 存在 aiai+1a_i \geq a_{i+1}
2 40%40\% 3\leq 3
3 40% 40\% 20\leq 20

对于全部数据,保证有 $1 \leq n \leq 20,1 \leq m \leq 10^5 , 1 \leq a_i \leq 1000$ 。

Source

GESP六级202406