题目描述

小杨想要计算由 ( m ) 个小写字母组成的字符串的得分。他设置了一个包含 ( n ) 个正整数的计分序列 ( A = [a1, a2,.... an] )。如果字符串的一个子串由 k( 1 ≤ k ≤ n )个 "abc" 首尾相接组成，那么能够得到分数 ( ak )。字符串包含的字符不能重复计算得分，整个字符串的得分是计分子串的总和。求给定字符串的最大总得分。

输入格式

• 第一行：一个正整数 ( 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≤20，1≤m≤$10^5$,1 ≤ai≤1000