计算得分

题面描述

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

小杨设置了一个包含 个正整数的计分序列 ，如果字符串的一个子串由 个 abc 首尾相接组成，那么能够得到分数 ，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。

例如，假设 ，字符串 dabcabcabcabzabc 的所有可能计分方式如下：

• d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc，其中 d 和 abz 不计算得分，总得分为
• d+abc+abc+abc+abz+abc，总得分为
• d+abcabcabc+abz+abc，总得分为

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

输入格式

第一行包含一个正整数 ，代表计分序列 的长度。

第二行包含 个正整数，代表计分序列 。

第三行包含一个正整数 ，代表字符串的长度。

第四行包含一个由 个小写字母组成的字符串。

输出格式

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

样例1

输入：

3
3 1 2
13
dabcabcabcabz

输出：

9

样例解释

最优的计分方式为 d+abc+abc+abc+abz，总得分为 ，共 9 分。

样例2

输入：

3
3 5 2
13
dabcabcabcabz

输出：

8

数据范围

对于全部数据，保证有 。

时间限制

1.0 s

内存限制

512.0 MB