4529 - 计算得分

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

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

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

例如，假设，字符串 $\texttt{dabcabcabcabzabc}$ 的所有可能计分方式如下：

$\texttt{d+abc+abcabc+abz+abc}$ 或者 $\texttt{d+abcabc+abc+abz+abc}$ ，其中 $\texttt{d}$ 和 $\texttt{abz}$ 不计算得分，总得分为 $a_1+a_2+a_1$ 。
$\texttt{d+abc+abc+abc+abz+abc}$ ，总得分为 $a_1+a_1+a_1+a_1$ 。
$\texttt{d+abcabcabc+abz+abc}$ ，总得分为 $a_3+a_1$ 。

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

输入

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

输出

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

样例

输入

3
3 1 2
13
dabcabcabcabz

输出

提示

样例解释

最优的计分方式为 $\texttt{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 \le n)$ ，存在 $ai \ge a{i+1}$
$2$	$40\%$	$\le 3$	$\le 10^5$	$\le 1000$
$3$	$40\%$	$\le 20$	$\le 10^5$	$\le 1000$

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

来源

GESP