题面描述

小杨想要计算由m个小写字母组成的字符串的得分。 小杨设置了一个包含n个正整数的计分序列$A=[a_1,a_2,\dots,a_n]$，如果字符串的一个子串由$k(1\leq k\leq 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$ 小杨想知道对于给定的字符串，最大总得分是多少。

  输入格式

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

   输出格式

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

   样例1

   输入

   3
   3 1 2
   13
   dabcabcabcabz

   输出

   9

   样例解释

   最优的计分方式为 $d+abc+abc+abc+abz$，总得分为$a_1+a_1+a_1=3\times3=9$。

   数据范围

   子任务编号	数据点占比	$n$	$m$	$a_i$	特殊条件
   1	20%	$\leq20$	$\leq10^5$	$\leq1000$	对于所有的$i(1\leq i<n)$，存在$ai \geq a{i+1}$
   2	40%	$\leq3$	$\leq10^5$	$\leq1000$	无
   3	40%	$\leq20$	$\leq10^5$	$\leq1000$	无

   全部数据满足：$1\leq n\leq20$，$1\leq m\leq10^5$，$1\leq a_i\leq1000$。