题目描述

小杨要计算一个小写字母串的最大得分。给定计分序列 $A$，若字符串的一个子串由 $k$ 个 abc 首尾相接组成（$1 \le k\le n$），则可获得 $a_k$ 分；各计分子串不能重叠。请计算整个字符串可获得的最大总分。

输入格式

第一行输入正整数 $n$。第二行输入 $n$ 个正整数 $a_i$。第三行输入正整数 $m$。第四行输入长度为 $m$ 的小写字母串。

输出格式

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

3
3 1 2
13
dabcabcabcabz

9

数据范围与提示

• $1 \le n\le 20$，$1 \le m\le 10^5$，$1 \le a_i \le 1000$。
• 只有形如 abcabc...abc 的连续子串可以计分，且同一字符不能被重复计分。

来源

GESP 2024 年 06 月 C++ 六级 T1