题目描述

小杨想要计算由 m 个小写字母组成的字符串的得分。 小杨设置了一个包含 n 个正整数的计分序列 a，如果字符串的一个子串由 j 个 abc 首尾相接组成（即连续 j 个 abc），那么能够得到分数 a[j]，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。 小杨想知道对于给定的字符串，最大总得分是多少。

输入格式

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

输出格式

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

样例 1

输入：

3
3 1 2
13
dabcabcabcabz

输出：

9

样例解释：最优的计分方式为 d + abc + abc + abc + abz，总得分 3 + 3 + 3 = 9 分。

数据范围

对于全部数据，保证有 1 ≤ n ≤ 27，1 ≤ a_i ≤ 10^4，1 ≤ m ≤ 1000。