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.
Example 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.
Example 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.
Unknwon for now. Will add once find them 🛵
input:
output: