Cho xâu \(S\) độ dài \(n\) chỉ gồm các chữ cái từ \(a\) đến \(z\).

Một xâu con liên tiếp của \(S\) được gọi là tệ nếu nó chỉ có một loại chữ cái.

Hãy tìm cách xóa đi đúng \(k\) ký tự sao cho số xâu con tệ của \(S\) sau khi xóa là nhỏ nhất, in ra số lượng xâu con tệ ít nhất có thể có.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(k\) \((1 \leq k \leq n \leq 10^{5})\).
• Dòng thứ hai là xâu \(S\) độ dài \(n\), chỉ gồm các chữ cái thường từ a đến z.

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(21\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(23\%\) số điểm): \(n \leq 28\).
• Subtask \(3\) (\(27\%\) số điểm): \(n \leq 5000\).
• Subtask \(4\) (\(29\%\) số điểm): Không có ràng buộc gì thêm.

Example

10 2
babbdddaaa

11

19 10
cbdccccaeebddceedce

9