COCI '22 Contest 4 #1 7Krokods

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem types

When he is not making videos for his YouTube channel, the famous programmer influencer Krokod likes to play boardgames with his friend Paula. He wants to play the game 7Krokods, but Paula doesn't like complex games, so Krokod decided that they will play only with green and crocodile cards.

Paula has $n$ ~n~ green cards, and each of them has one of the following letters written on it: d, k, o, or r. Her total score is defined as the sum of the following components:

For each letter, she gets as many points as is the number of cards with that letter written on them, squared. For example, if she has $6$ ~6~ cards with the letter k, she gets $36$ ~36~ points.
For each word krokod she can make from her cards, she gets an extra $7$ ~7~ points.

Illustration of the first example.

Paula has $2$ ~2~ letters d $(2 \cdot 2 = 4 \text{ points})$ ~(2 \cdot 2 = 4 \text{ points})~, $6$ ~6~ letters k $(6 \cdot 6 = 36 \text{ points})$ ~(6 \cdot 6 = 36 \text{ points})~, $4$ ~4~ letters o $(4 \cdot 4 = 16 \text{ points})$ ~(4 \cdot 4 = 16 \text{ points})~ and $3$ ~3~ letters r $(3 \cdot 3 = 9 \text{ points})$ ~(3 \cdot 3 = 9 \text{ points})~. The word krokod can be spelled $2$ ~2~ times $(7 \cdot 2 = 14 \text{ points})$ ~(7 \cdot 2 = 14 \text{ points})~. Her total score is $79$ ~79~. $(4 + 36 + 16 + 9 + 14 = 79)$ ~(4 + 36 + 16 + 9 + 14 = 79)~

Paula also has $m$ ~m~ crocodile cards. She can replace each of the crocodile cards with a green card having a letter of her choice. She will do it in a way that maximizes her score.

Help her determine the maximum score she can get with her cards.

Input Specification

The first line contains integers $n$ ~n~ and $m$ ~m~ $(0 \le n \le 100, 0 \le m \le 10)$ ~(0 \le n \le 100, 0 \le m \le 10)~, the number of green cards and the number of crocodile cards.

The second line contains a sequence of $n$ ~n~ characters, where the $i^\text{th}$ ~i^\text{th}~ character represents the letter on the $i^\text{th}$ ~i^\text{th}~ green card. The sequence consists only of characters d, k, o and r.

Output Specification

In the first and only line, output Paula's maximum possible score.

Constraints

Subtask	Points	Constraints
1	17	$m = 0$ ~m = 0~
2	26	$m = 1$ ~m = 1~
3	7	No additional constraints.

Sample Input 1

15 0
krokodkrokodkrk

Sample Output 1

Explanation for Sample 1

Look at the illustration in the task statement.

Sample Input 2

5 1
rokod

Sample Output 2

Explanation for Sample 2

For the maximum possible score, Paula can replace her crocodile card with a green card having the letter k.

Sample Input 3

8 2
ddkkoorr

Sample Output 3

Comments

There are no comments at the moment.