Maximum Score from abc Substrings

Given a string consisting of m lowercase letters and a scoring sequence of n positive integers \(A = [a_1, a_2, \ldots, a_n]\), your task is to calculate the maximum total score by selecting some disjoint scoring substrings.

A valid scoring substring is defined as exactly k consecutive repetitions of the string abc (i.e. it equals \( (abc)^k \)) for some \(1 \le k \le n\). When you select such a substring, it contributes a score of \(a_k\). Note that no character in the string may be used in more than one scoring substring.

For example, consider \(A = [a_1, a_2, a_3]\) and the string dabcabcabcabzabc. One possible optimal segmentation is:

• Segment the string as: d + abc + abcabc + abz + abc
• This yields a score of \(a_1 + a_2 + a_1\) (since the segments d and abz do not contribute).

Your goal is to determine the maximum total score obtainable.

inputFormat

The input consists of the following:

1. The first line contains two integers \(n\) and \(m\) — the length of the scoring sequence and the length of the string, respectively.
2. The second line contains \(n\) space-separated positive integers representing \(a_1, a_2, \ldots, a_n\).
3. The third line contains a string of \(m\) lowercase letters.

outputFormat

Output a single integer — the maximum total score that can be achieved by choosing disjoint scoring substrings.

sample

3 17
1 2 3
dabcabcabcabzabc

4