Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1154.

Problem Description

Xiao Yang wants to calculate the score of a string consisting of $m$ lowercase letters.

Xiao Yang sets a scoring sequence $A=[a_1,a_2,\ldots,a_n]$ of $n$ positive integers. If a substring of the string is formed by concatenating $k(1\leq k \leq n)$ copies of $\texttt{abc}$ end to end, then it can gain a score of $a_k$. Also, characters in the string cannot be counted repeatedly for scoring. The total score of the whole string is the sum of the scores of the scoring substrings.

For example, suppose the string is $\texttt{dabcabcabcabzabc}$. All possible scoring methods are as follows:

• $\texttt{d+abc+abcabc+abz+abc}$ or $\texttt{d+abcabc+abc+abz+abc}$, where $\texttt{d}$ and $\texttt{abz}$ do not score, and the total score is $a_1+a_2+a_1$.
• $\texttt{d+abc+abc+abc+abz+abc}$, and the total score is $a_1+a_1+a_1+a_1$.
• $\texttt{d+abcabcabc+abz+abc}$, and the total score is $a_3+a_1$.

Xiao Yang wants to know, for a given string, what the maximum total score is.

Input Format

• The first line contains a positive integer $n$, representing the length of the scoring sequence $A$.

• The second line contains $n$ positive integers, representing the scoring sequence $A$.

• The third line contains a positive integer $m$, representing the length of the string.

• The fourth line contains a string of $m$ lowercase letters.

Output Format

Output one integer, representing the maximum total score of the given string.

3
3 1 2
13
dabcabcabcabz

9

Hint

Sample Explanation

The best scoring method is $\texttt{d+abc+abc+abc+abz}$, and the total score is $a_1+a_1+a_1$, which is $9$ points in total.

Constraints

For all testdata, it is guaranteed that $1\leq n\leq 20$, $1\leq m\leq 10^5$, and $1\leq a_i\leq 1000$.

Translated by ChatGPT 5