题目描述

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

小杨设置了一个包含 n 个正整数的计分序列 A=[a_1,a_2,…,a_n]，如果字符串的一个子串由 j（1≤j≤n）个 abc 首尾相接组成，那么能够得到分数 a_j，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。

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

输入格式

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

输出格式

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

样例

样例输入 1

3
3 1 2
13
dabcabcabcabz

样例输出 1

9

样例解释

样例中，最优计分方式为 d+abc+abc+abc+abz，总得分为 a_1+a_1+a_1=9。

数据范围

原卷数据范围：1≤n≤20，1≤m≤10^5，1≤a_i≤10^3；部分子任务还保证计分序列满足额外单调条件。