Maximizing Score in 7Krokods Game with Green and Croc Cards

Paula is playing a board game with Krokod using two types of cards: green cards and crocodile (croc) cards. She has n green cards, each bearing one of the letters from the set {d, k, o, r}. Her score is defined as the sum of two parts:

• For each letter, she gets points equal to the square of the total number of cards (green plus substitutions) bearing that letter. For example, if she ends up with 6 cards marked k, she scores 36 points for that letter.
• Additionally, every time she is able to assemble the word krokod (which consists of the letters k, r, o, k, o, d), she earns an extra 7 points.

Paula also has m crocodile cards. Each crocodile card can substitute for any green card – that is, you may choose a letter (d, k, o, or r) for the crocodile card, and it will count as a green card with that letter.

Your task is to maximize Paula’s total score. In other words, by distributing the m croc cards optimally among the letters (thereby increasing the counts for the letters) and choosing how many times to form the bonus word "krokod", compute the maximum total score.

Important notes:

• The bonus can be claimed only if, for each letter, the final count is at least equal to the number of times that letter is required in "krokod". In particular, the word "krokod" requires: 2 k, 1 r, 2 o and 1 d.
• You must decide how many bonus words to form (let this number be x) and how to distribute the crocodile cards to satisfy the requirements for these bonus words. The remaining crocodile cards may be allocated arbitrarily to maximize the sum of squares.

The final score is computed as follows:

[ \text{score} = \sum_{\ell \in {d,k,o,r}} (a_\ell)^2 + 7\times x, ]

where for each letter \(\ell\), the final count \(a_\ell\) is the sum of the green cards originally showing \(\ell\) and the crocodile cards assigned to \(\ell\). To be able to claim x bonus words, the counts must satisfy:

[ \begin{aligned} a_d &\ge x,\ a_k &\ge 2x,\ a_o &\ge 2x,\ a_r &\ge x.\ \end{aligned} ]

You are allowed to use the crocodile cards to satisfy these inequalities. Let

[ \text{needed}_\ell = \max(0, (\text{required count for }\ell) \times x - (\text{original count of }\ell)). ]

Then if \(\text{needed}_d + \text{needed}_k + \text{needed}_o + \text{needed}_r \le m\), it is possible to form x bonus words. The extra substitutions left after fulfilling these requirements can be allocated arbitrarily to any letter to further increase the squared sum.

Your task is to compute the maximum possible score Paula can achieve.

inputFormat

The first line contains two integers n and m (0 \le n, m \le 10^5), representing the number of green cards and the number of crocodile cards, respectively.

The second line is a string of length n consisting only of the characters d, k, o, and r, representing the letters on the green cards.

outputFormat

Output a single integer, the maximum score that Paula can achieve.

sample

6 0
krokod

17