题目描述

小杨有一个由 m 个小写字母组成的字符串 s。他设置了一个计分规则：如果字符串的一个子串是由连续 k 个 "ab" 组成的（即 "ab" 重复 k 次），那么该子串可以获得分数 a_k。字符串中的字符只能被一个得分子串使用。整个字符串的得分是所有得分子串的得分之和。

小杨想知道如何选择得分子串使得总得分最大。

输入格式

• 第一行一个正整数 n，表示计分序列的长度。
• 第二行 n 个正整数，表示计分序列 A = [a_1, a_2, ..., a_n]。
• 第三行一个正整数 m，表示字符串的长度。
• 第四行一个由 m 个小写字母组成的字符串 s。

输出格式

输出一个整数，表示最大总得分。

样例输入

2
1 10
6
ababab

样例输出

11

样例解释

字符串 "ababab" 可以划分为 "abab"（由 2 个 "ab" 组成，得分 a_2 = 10）和 "ab"（由 1 个 "ab" 组成，得分 a_1 = 1），总得分 11。如果划分为三个 "ab"，得分为 3 × 1 = 3，不如 11 大。

数据范围

• 1 ≤ n ≤ 20
• 1 ≤ m ≤ 10^5
• 1 ≤ a_i ≤ 1000