COCI '22 Contest 4 #1 7Krokods

View as PDF

Submit solution

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 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 cards with the letter k, she gets 36 points.
  • For each word krokod she can make from her cards, she gets an extra 7 points.
Illustration of the first example. Paula has 2 letters d (2 \cdot 2 = 4 \text{ points}), 6 letters k (6 \cdot 6 = 36 \text{ points}), 4 letters o (4 \cdot 4 = 16 \text{ points}) and 3 letters r (3 \cdot 3 = 9 \text{ points}). The word krokod can be spelled 2 times (7 \cdot 2 = 14 \text{ points}). Her total score is 79. (4 + 36 + 16 + 9 + 14 = 79)

Paula also has 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 and m (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 characters, where the i^\text{th} character represents the letter on the 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.


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

Sample Input 1

15 0

Sample Output 1


Explanation for Sample 1

Look at the illustration in the task statement.

Sample Input 2

5 1

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

Sample Output 3



There are no comments at the moment.