Keyboard Purchase

题意翻译

      一个密码：一个长度为n的字符串s，其字符均为前m个小写字母。       键盘是前m个字母的排列组合，若m=3，则有：abc，acb，bac，bca，cab，cba，**6种键盘**。       因为你只用一个手指输入密码，所以你需要花时间把手指从一个字符移到另一个字符，从si移到si+1的时间等于键盘上这些字符之间的距离。 - 你的密码为aacabc ，你选择键盘bac，则所需的总时间为： |posa−posa|+|posa−posc|+|posc−posa|+|posa−posb|+|posb−posc|=|2−2|+|2−3|+|3−2|+|2−1|+|1−3| = 0+1+1+1+2=5. - 总时间 = ∑i=2~n|pos_si−1 − pos_si|, 求输入密码所用的最少时间，你可以选择任意一种键盘。

题目描述

You have a password which you often type — a string $ s $ of length $ n $ . Every character of this string is one of the first $ m $ lowercase Latin letters. Since you spend a lot of time typing it, you want to buy a new keyboard. A keyboard is a permutation of the first $ m $ Latin letters. For example, if $ m = 3 $ , then there are six possible keyboards: abc, acb, bac, bca, cab and cba. Since you type your password with one finger, you need to spend time moving your finger from one password character to the next. The time to move from character $ s_i $ to character $ s_{i+1} $ is equal to the distance between these characters on keyboard. The total time you have to spend typing the password with a keyboard is called the slowness of this keyboard. More formaly, the slowness of keyboard is equal to $ \sum\limits_{i=2}^{n} |pos_{s_{i-1}} - pos_{s_i} | $ , where $ pos_x $ is position of letter $ x $ in keyboard. For example, if $ s $ is aacabc and the keyboard is bac, then the total time of typing this password is $ |pos_a - pos_a| + |pos_a - pos_c| + |pos_c - pos_a| + |pos_a - pos_b| + |pos_b - pos_c| $ = $ |2 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 3| $ = $ 0 + 1 + 1 + 1 + 2 = 5 $ . Before buying a new keyboard you want to know the minimum possible slowness that the keyboard can have.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^5, 1 \le m \le 20 $ ). The second line contains the string $ s $ consisting of $ n $ characters. Each character is one of the first $ m $ Latin letters (lowercase).

输出格式

Print one integer – the minimum slowness a keyboard can have.

输入输出样例

输入样例 #1

6 3
aacabc

输出样例 #1

5

输入样例 #2

6 4
aaaaaa

输出样例 #2

0

输入样例 #3

15 4
abacabadabacaba

输出样例 #3

16

说明

The first test case is considered in the statement. In the second test case the slowness of any keyboard is $ 0 $ . In the third test case one of the most suitable keyboards is bacd.