Sau khi đi du lịch từ thành phố Alpha về, Steve vẫn còn dư tiền thưởng và quyết định đi mua bàn phím mới để phục vụ cho công việc gõ mật khẩu. Mật khẩu là một xâu 𝑠 có độ dài là 𝑛. Mỗi kí tự của xâu này là một trong 𝑚 kí tự đầu tiên trong bản chữ cái Latin in thường. Bàn phím thế hệ mới là một hoán vị của 𝑚 chữ cái Latin in thường đầu tiên được xếp theo một hàng ngang từ trái sang phải.

Ví dụ, nếu 𝑚 = 3 thì có 6 bàn phím khác nhau là: \(abc,\ acb,\ bac,\ bca,\ cab\) và \(cba\). Vì Steve chỉ gõ mật khẩu với một ngón tay nên cần thời gian để di chuyển từ một kí tự trong mật khẩu sang kí tự tiếp nối nó. Thời gian Steve dùng để di chuyển từ kí tự 𝑠_𝑖 sang kí tự 𝑠_𝑖+1 bằng với khoảng cách của hai kí tự này trên bàn phím. Thời gian tổng cộng mà Steve cần để gõ mật khẩu s với một bàn phím nhất định thì được gọi là độ chậm của bàn phím đó. Steve muốn mua bàn phím có độ chậm nhỏ nhất.

Định nghĩa cụ thể hơn, độ chậm của một bàn phím thì bằng

\[\sum_{i = 2}^{n}\left| \ pos\left( s_{i - 1} \right) - pos\left( s_{i} \right) \right|\]

Với 𝑝𝑜𝑠(𝑥) là vị trí của kí tự 𝑥 trên bàn phím.

Ví dụ, nếu 𝑠 là \(aacabc\) và bàn phím là \(bac\), thì tổng thời gian để gõ mật khẩu là:

\(\left| pos(a) - pos(a) \right| + \ \left| pos(a) - pos(c) \right| + \left| pos(c) - pos(a) \right| + \left| pos(a) - pos(b) \right| + \left| pos(b) - pos(c) \right| = |2 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 3| = 0 + 1 + 1 + 1 + 2 = 5\)

Yêu cầu: Cho trước xâu kí tự \(s\) là mật khẩu Steve hay phải gõ, hãy giúp Steve chọn mua bàn phím có độ chậm nhỏ nhất.

Dữ liệu:

+ Dòng đầu tiên chứa hai số nguyên dương \(n,\ m\ (1 \leq n \leq 10^{5};1 \leq m \leq 20)\).

+ Dòng thứ hai chứa một xâu \(s\) có \(n\) kí tự. Mỗi kí tự là một trong 𝑚 chữ cái Latin đầu tiên (in thường).

Kết quả:

+ Ghi một số nguyên là độ chậm nhỏ nhất mà một bàn phím có thể có.

Ví dụ:

Giải thích: Ví dụ đầu tiên được xem xét trong đề bài. Trong ví dụ thứ hai, bàn phím tốt nhất là \(bacd\).

Ghi chú:

+ Subtask 1: 10% số test có \(0 < m \leq 2\);

+ Subtask 2: 30% số test có \(2 < m \leq 10\);

+ Subtask 3: 60% số test có \(10 < m \leq 20\).