Có \(N\) người được sắp xếp thành một hàng từ trái sang phải.

Bạn được cho một chuỗi \(S\) có độ dài \(N\) bao gồm các ký tự \(0\) và \(1\), và một số nguyên dương \(K\).

Người thứ \(i\) từ bên trái đang đứng bằng chân nếu ký tự thứ \(i\) của \(S\) là \(0\), và đang đứng bằng tay nếu ký tự đó là \(1\).

Bạn sẽ đưa ra hướng dẫn sau đây nhiều nhất \(K\) lần (có thể là không lần nào):

Hướng dẫn: Chọn các số nguyên \(l\) và \(r\) thỏa mãn \(1 \leq l \leq r \leq N\), và lật ngược các người từ \(l\) đến \(r\). Nghĩa là, với mỗi \(i=l,l+1,...,r\), người thứ \(i\) từ bên trái bây giờ sẽ đứng bằng tay nếu trước đó đứng bằng chân, và đứng bằng chân nếu trước đó đứng bằng tay.

Tìm số lượng tối đa người liên tiếp đang đứng bằng tay sau nhiều nhất \(K\) lần hướng dẫn.

Ràng buộc

• \(N\) là một số nguyên thỏa mãn \(1 \leq N \leq 10^5\).
• \(K\) là một số nguyên thỏa mãn \(1 \leq K \leq 10^5\).
• Độ dài của chuỗi \(S\) là \(N\).
• Mỗi ký tự của chuỗi \(S\) là \(0\) hoặc \(1\).

INPUT FORMAT

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

N
K
S

OUTPUT FORMAT

In ra số lượng tối đa người liên tiếp đang đứng bằng tay sau nhiều nhất \(K\) lần hướng dẫn.

Ví dụ:

Input

5 1
00010

Output

4

Chúng ta có thể có bốn người liên tiếp đang đứng bằng tay, đây là kết quả tối đa, bằng cách đưa ra hướng dẫn sau:

Cho hướng dẫn với \(l=1, r=3\), lật ngược người thứ nhất, thứ hai và thứ ba từ bên trái.

Input

14 2
11101010110011

Output

8

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  5 1 00010

• Giải thích:

  • Lật ngược ba người đầu tiên (1 đến 3) sẽ tạo ra chuỗi 11110, cho phép có bốn người liên tiếp đứng bằng tay.

Ví dụ 2:

• Input:

  14 2 11101010110011

• Giải thích:

  • Thực hiện hai lần lật ngược có thể tạo ra chuỗi với tám người đứng bằng tay liên tiếp, là kết quả tối đa có thể đạt được.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House