字符串计分

题目描述

Y 同学正在研究一种基于特定模式的字符串计分系统。

给定一个长度为 $N$ 的计分序列 $A = \{a_1, a_2, \ldots, a_N\}$。 同时给定一个由小写字母组成的、长度为 $M$ 的字符串 $S$。

定义一个 $k$ 阶模式串 为字符串 abc 重复拼接 $k$ 次的结果。 例如：

• $1$ 阶模式串为 abc。
• $2$ 阶模式串为 abcabc。
• $k$ 阶模式串的长度为 $3k$。

Y 同学需要将字符串 $S$ 划分为若干个不重叠的子串。对于每一个划分出的子串，如果它恰好是一个 $k$ 阶模式串（其中 $1 \le k \le N$），那么 Y 同学就可以获得 $a_k$ 的分数。字符串中未被匹配的字符不产生分数。每个字符至多只能属于一个计分子串。

请你帮助 Y 同学规划划分方案，计算出能够获得的最大总得分。

输入格式

第一行包含一个正整数 $N$，表示计分序列的长度。 第二行包含 $N$ 个正整数 $a_1, a_2, \ldots, a_N$，表示各阶模式串对应的分数。 第三行包含一个正整数 $M$，表示字符串 $S$ 的长度。 第四行包含一个由 $M$ 个小写字母组成的字符串 $S$。

输出格式

输出一行一个整数，表示能够获得的最大总得分。

样例

样例输入 #1

3
3 1 2
13
dabcabcabcabz

样例输出 #1

9

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 20$，$1 \le M \le 10^5$，$1 \le a_i \le 1000$。字符串 $S$ 仅包含小写英文字母。