405179: GYM101810 G Power of String

Yosef Darwish is participating this year in the ACM International Collegiate Programming Contest (ACM ICPC). Unfortunately, Yosef had an argument with his team because he wanted to name the team "yosefdarwish" but his team refused because the power of this name was too low.

Let the power of a string S of length n be defined as P(S), in which:

in which N_i is the number of indices j (i < j ≤ n) such that S_i ≡ S_j, and V_i is the ASCII value in decimal of character S_i.

You are given a string s of length n consisting of lowercase English letters, and an integer k. You are allowed to make at most k change operations, such that at each operation you can change any letter s_i to any other lowercase English letter. Your task is to use the change operations to maximize the power of string s. Can you?

The first line contains an integer T (1 ≤ T ≤ 10) specifying the number of test cases.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 5000), in which n is the length of string s, and k is the number of allowed change operations. Then a line follows containing string s of length n consisting of lowercase English letters.

For each test case, print a single line containing the maximum power of string s after making at most k change operations.

2
12 1
yosefdarwish
5 1
aaaaz

345
970

American Standard Code for Information Interchange (ASCII) is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Lowercase 'a' has ASCII value 97 in decimal, lowercase 'b' has ASCII value 98 in decimal, and so on. Lowercase 'z' has ASCII value 122 in decimal.