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\%~ số test ứng với ~25\%~ số điểm có ~N \le 20~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~N \le 100~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~N \le 5000~;
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm không có ràng buộc gì thêm.