题面描述

小杨想要计算由m个小写字母组成的字符串的得分。 小杨设置了一个包含n个正整数的计分序列A=[a1,a2,...,an]，如果字符串的一个子串由k（1≤k≤n）个abc首尾相接组成，那么能够获得分数ak，且字符串中的每个字符只能被一个计分子串使用，整个字符串的总得分是所有计分子串的分数之和。

例如，当n=3时，字符串dabcabcabcabzabc的几种计分方式如下：

1. d+ac+abcabc+abz+abc或d+abcac+ac+abz+abc，其中d和abz不参与计分，总得分为a1+a2+a1
2. d+abc+abc+abc+abz+abc，总得分a1+a1+a1+a1
3. d+abcabcabc+abz+abc，总得分为a3+a1

小杨需要求出给定字符串的最大总得分。

输入格式

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

输出格式

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

样例输入

3
3 1 2
13
dabcabcabcabz

样例输出

9

样例解释

最优的计分方式为d+abc+abc+abc+abz，总得分a1+a1+a1，对应分数为3+3+3=9。

数据范围

对于全部测试数据，满足1 ≤ n ≤ 20, 1 ≤ m ≤ 10^5, 1 ≤ ai ≤ 1000。

子任务划分： | 子任务编号 | 数据点占比 | $n$ | $m$ | $a_i$ | 特殊条件 | |------------|------------|-----------|-----------|------------|------------------------------------------------| | 1 | 20% | $≤20$ | $≤10^5$ | $≤1000$ | 对于所有$1≤i<n$，满足$ai ≥ a{i+1}$ | | 2 | 40% | $≤3$ | $≤10^5$ | $≤1000$ | 无 | | 3 | 40% | $≤20$ | $≤10^5$ | $≤1000$ | 无 |