Cho một xâu gồm $m$ loại kí tự khác nhau (chỉ bao gồm các chữ cái tiếng Anh in hoa) và hai loại thao tác xoá như sau:

• Thao tác $1$: Xoá kí tự đầu hoặc kí tự cuối của xâu;
• Thao tác $2$: Xoá một kí tự ở giữa xâu.

Yêu cầu: Cho xâu $S$ gồm $N$ kí tự, hãy tìm cách sử dụng các thao tác xoá xâu để thoả mãn các điều kiện sau:

• Dùng tối thiểu thao tác $2$;
• Xâu còn lại chỉ còn đúng $m\times k$ kí tự;
• Mỗi loại kí tự chỉ xuất hiện đúng $k$ lần.

Dữ liệu vào từ tệp văn bản DELSTR.INP:

• Dòng đầu tiên chứa hai số $m,k$ $(2\le m\le 26)$;
• Dòng tiếp theo chứa xâu $S$ $(2\le m\times k\le N\le 2\times {10}^5)$.

Kết quả ghi ra tệp văn bản DELSTR.OUT:

Gồm một số nguyên duy nhất là số thao tác $2$ ít nhất được sử dụng để thoả mãn yêu cầu đề bài.

Ví dụ

Input

3 2
ABBABCABBCCCBA

Output

1

Giải thích

• Sử dụng thao tác $1$: Xoá $3$ kí tự đầu và $4$ kí tự cuối.
• Sau đó dùng $1$ lần thao tác $2$ xoá kí tự $B$ còn thừa ở giữa.

$\Rightarrow$ Thu được xâu: ABCABC thoả mãn có đúng $3\times 2=6$ kí tự và mỗi kí tự xuất hiện đúng $2$ lần.

Input

3 2
ABABAAACCC

Output

2

Giải thích

• Xoá $1$ kí tự đầu và $1$ kí tự cuối, sau đó dùng hai lần thao tác $2$ xoá kí tự $A$ còn thừa ở giữa.

Ràng buộc

• Có $25\mathrm{\%}$ số test ứng với $25\mathrm{\%}$ số điểm có $N\le 20$;
• $25\mathrm{\%}$ số test khác ứng với $25\mathrm{\%}$ số điểm có $N\le 100$;
• $25\mathrm{\%}$ số test khác ứng với $25\mathrm{\%}$ số điểm có $N\le 5000$;
• $25\mathrm{\%}$ số test còn lại ứng với $25\mathrm{\%}$ số điểm không có ràng buộc gì thêm.