计算得分

题目描述

小杨想要计算由 $m$ 个小写字母组成的字符串的得分。 小杨设置了一个包含 $n$ 个正整数的计分序列 $A = [a_1, a_2, \cdots, a_n]$，如果字符串的一个子串由 $k$ ($1 \le k \le n$) 个 abc 首尾相接组成，那么能够得到分数 $a_k$，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。 例如，假设 $n = 3$，字符串 dabcabcabcabzabc 的所有可能计分方式如下： d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc，其中 d 和 abz 不计算得分，总得分为 $a_1 + a_2 + a_1$。 d+abc+abc+abc+abz+abc，总得分为 $a_1 + a_1 + a_1 + a_1$。 d+abcabcabc+abz+abc，总得分为 $a_3 + a_1$。 小杨想知道对于给定的字符串，最大总得分是多少。

输入格式

第一行包含一个正整数 $n$，代表计分序列 $A$ 的长度。 第二行包含 $n$ 个正整数，代表计分序列 $A$。 第三行包含一个正整数 $m$，代表字符串的长度。 第四行包含一个由 $m$ 个小写字母组成的字符串。

输出格式

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

输入样例 1

3
3 1 2
13
dabcabcabcabz

输出样例 1

9

样例解释 1

最优的计分方式为 d+abc+abc+abc+abz，总得分为 $a_1 + a_1 + a_1$，共 9 分。

数据范围

子任务编号 数据点占比 $n$ $m$ $a_i$ 特殊条件

1 20% $\le 20$ $\le 10^5$ $\le 1000$ 对于所有的 $i$ ($1 \le i < n$)，存在 $a_i \ge a_{i+1}$
2 40% $\le 3$ $\le 10^5$ $\le 1000$
3 40% $\le 20$ $\le 10^5$ $\le 1000$

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