P9172 [COCI 2022/2023 #4] 7Krokods

[Enhanced version](/problem/U382344) [Second enhanced version](/problem/U502888)

Krokod likes playing board games with Paula. He wants to play the 7Krokods game, but Paula does not like complicated games, so Krokod decided that they will play using only green cards and crocodile cards. Paula has $n$ green cards, and each card has one of the following letters written on it: $d, k, o, r$. Her total score is defined as the sum of the following parts. - For each letter, she gets a score equal to the square of the number of cards with that letter. For example, if she has $6$ cards with the letter $k$, she gets $36$ points. - For each time she forms the word `krokod`, she gets an additional $7$ points. Paula also has $m$ crocodile cards. She can use any crocodile card to replace a green card, with the green card having any letter she chooses. Compute the maximum score she can get from her cards.

The first line contains two integers $n$ and $m(0\leq n\leq 100,0\leq m\leq 10)$, representing the number of green cards and the number of crocodile cards. The second line contains a sequence of $n$ characters, where the $i$-th character represents the letter on the $i$-th green card. The sequence consists only of the characters $d, k, o, r$.

Output one integer in a single line, the maximum possible score Paula can achieve.

Explanation for Sample $1$:  Paula has $2$ letters $d$ ($2\times 2=4$ points), $6$ letters $k$ ($6\times 6=36$ points), $4$ letters $o$ ($4\times 4=16$ points), and $3$ letters $r$ ($3\times 3 = 9$ points). The word `krokod` can be formed $2$ times ($7\times 2=14$ points). Her total score is $79$ ($4 + 36 + 16 + 9 + 14 = 79$). Explanation for Sample $2$: Paula can turn her crocodile card into a green card with the letter $k$ written on it. | Subtask ID | Additional Constraints | Score | | :-: | :-: | :-: | | $0$ | Sample | $0$ | | $1$ | $m=1$ | $17$ | | $2$ | $m=2$ | $26$ | | $3$ | No additional constraints | $7$ | Translated by ChatGPT 5