Cho một xâu nhị phân ~s~ có độ dài ~n~ và một số nguyên ~k~. Thực hiện tối đa ~k~ operations hoán đổi hai phần tử liền kề trong xâu sao cho số phần tử kề nhau mà khác nhau được cực đại hóa.

Nói theo một cách khác, ta được phép thực hiện tối đa ~k~ lần operation sau: chọn một vị trí ~i~ ~(1 \leq i \leq n - 1)~, hoán đổi hai kí tự ~s_i~ và ~s_{i + 1}~.

Sau khi thực hiện ~k~ operations, tính số vị trí ~i~ nhiều nhất có thể thỏa mãn ~(1 \leq i \leq n - 1)~ và ~s_i \neq s_{i+1}~.

Input

Dòng đầu tiên chứa hai số nguyên ~2 \leq n \leq 300 , k \leq 10^9~.

Dòng thứ hai chứa một xâu nhị phân độ dài ~n~.

Output

In ra số vị trí thỏa yêu cầu đề bài sau khi thực hiện các operations một cách tối ưu.

Scoring

• Subtask ~1~ (chiếm ~5\%~ số điểm): ~n \leq 3~

• Subtask ~2~ (chiếm ~10\%~ số điểm): ~n \leq 20~

• Subtask ~3~ (chiếm ~85\%~ số điểm): không có ràng buộc gì thêm

Sample Input 1

5 3
01100

Sample Output 1

4

Sample Input 2

10 12
0110101000

Sample Output 2

8

Notes

Ở test ví dụ thứ nhất, có thể hoán đổi hai vị trí ~3~ và ~4~ để nhận được xâu ~01010~.

Ở test ví dụ thứ hai, ta có thể làm như sau

• Hoán đổi vị trí ~3~ và ~4~, nhận được xâu ~0101101000~

• Hoán đổi vị trí ~5~ và ~6~, nhận được xâu ~0101011000~

• Hoán đổi vị trí ~7~ và ~8~, nhận được xâu ~0101010100~