Problem C
Naming Babies
Every parent wants to have their child the most beautiful name. Everyone will call their beloved child using the name. If someday the child gets to be famous then he/she will be known by the name. So name is very important. But choosing name is not that easy for the people nowadays because the government have decided to put tax on the name.
You will be given a perfect name PN consisting of every character from ‘a’-‘z’ only once (That is permutation of lower case English alphabet). The tax of a name will be calculated with reference to PN. Suppose PN = “abcdefghijklmnopqrstuvwzyx”. For a name NM, the tax is the summation of taxes for its each character. Suppose the ith character of NM is Ci . Let POS be the position of Ci in PN. So the tax for Ci will be (i – POS)*POS.
Suppose NM = “abazz”. So the taxes are:
i = 0, C0 = ‘a’, POS = 0, tax = (0 – 0)*0 = 0
i = 1, C1 = ‘b’, POS = 1, tax = (1 – 1)*1 = 0
i = 2, C2 = ‘a’, POS = 0, tax = (2 – 0)*0 = 0
i = 3, C3 = ‘z’, POS = 23, tax = (3 – 23)*23 = -460
i = 4, C4 = ‘z’, POS = 23, tax = (4 – 23)*23 = -437
So total tax for NM is 0 + 0 + 0 – 460 – 437 = -897. As this is negative, that means instead of giving tax to government, government will pay 897 Tk to the name-holder’s parent.
Now the parents are applying a very clever trick. You can understand very easily that the longer a name the greater its tax. So after fixing a particular name NM, they are splitting it into exactly K parts (this value K is enforced by government). Each of this K parts are considered as a single name and thus the total tax becomes much less. For example if we split the name in the earlier example in two parts “aba” and “zz” the taxes becomes 0 (0 + 0 + 0) and -1035 (-529 – 506) [Here, 0 is the cost of “aba” and -1035 is the cost for “zz”. That is- calculate tax separately for each of the K parts.]. So the sum is -1035 which is less than -895.
Now, given PN, NM and K, you need to find the minimum tax.
Input
First line will contain the number of test case, T (T <= 10). Each case will contain PN and K (0 < K <= 500) in the first line. The next line will contain a not empty string NM. Length of NM will be at most 20000 and greater than or equals to K and will consist of only lowercase letters.
Output
For each case print one line, “Case C: TX” (without the quotes), where C is the case number and TX is minimum tax.
|
Sample Input |
Output for Sample Input |
|
3 abcdefghijklmnopqrstuvwzyx 2 abazz abcdefghijklmnopqrstuvwxyz 2 abazz abcdefghijklmnopqrstuvwzyx 3 aabbbccccccccc |
Case 1: -1035 Case 2: -1225 Case 3: 2 |
Explanation
3 parts for the last sample are “aabbb”, “cccc” and “ccccc”. The corresponding taxes are 6 (0 + 0 + 1 + 2 + 3), -4 (-4 -2 + 0 + 2) and 0 (-4 -2 + 0 + 2 + 4).
So total tax is 6 – 4 + 0 = 2.
Problemsetter: Hasnain Heickal
Special Thanks: Md. Mahbubul Hasan