FastPrepFastPrep
Problem Brief

Letter Candles

OA

Your friend Alice has a box with N letter candles in it. The cost of the box is determined as follows - Find the number of occurrences of each character in the box and sum up the squares of these numbers.

Alice wants to reduce the cost of the box by removing some candles from it. However, she is allowed to remove at most M candles from the box. Can you help Alice determine the minimum cost of the box?

Input

The first line of the input contains the integer N, representing the number of letter candles. The second line of the input contains the integer M, representing the number of candles Alice can remove. The third line of the input contains an N-lettered string S, which contains lowercase English letters, representing the letter candles in the box.

Output

Print the minimum possible cost of the box.

1Example 1

Input
n = 6, m = 2, s = "bacaac"
Output
6
Explanation

There are two As, one B, and three Cs in the box. Current cost of the box is 2^2 + 1^2 + 3^2 = 14. The best way to minimize the cost of the box is to remove two C-shaped candles from it. The new minimal cost will be 2^2 + 1^2 + 1^2 = 6. The answer is 6.

2Example 2

Input
n = 15, m = 3, s = "xxxxxxxxxxxxxxx"
Output
144
Explanation

There are 15 Xs. The current cost of the box is 15^2 = 225. The only way to minimize the cost is by reducing three X-shaped candles from it. The new minimal cost will be 12^2 = 144. The answer is 144.

Constraints

Limits and guarantees your solution can rely on.

Unknwon for now. Will add once find them 🛵
public int minimumCost(int n, int m, String s) {
    // write your code here
}
Input

n

6

m

2

s

"bacaac"

Output

6

Sign in to submit your solution.