K-String

Codeware19: Intra AUST Pr...
Limits 1s, 512 MB

We will call a string KK-String if it consists of KK distinct characters. For example, if KK is 3 then “abc”, “aabbcc”, “xyaaaa” are KK-String whereas “abcd”, “ddhhnnggs” are not.

In one move, you can replace any one character of the given string by any other lower case English alphabet. Your task is to find the minimum number of moves required to make a string KK-String.

It is guaranteed that you can always convert the given string into a KK-string by performing zero or more moves.

Input

The first line of the input contains two integers NN (1N1061 ≤ N ≤ 10^6), denoting the size of the string and KK (1K261 ≤ K ≤ 26), denoting the number of distinct characters required.

Output

Output the minimum number of moves required to make the given string a KK-String.

Samples

InputOutput
4 3
abcd
1
InputOutput
5 3
abcdd
1

Submit

Login to submit.

Statistics

62% Solution Ratio
Double_OEarliest, Sep '19
poisonousFastest, 0.0s
yuv_sustLightest, 131 kB
Nusab19Shortest, 131B
Toph uses cookies. By continuing you agree to our Cookie Policy.