이어지는 충전 구역

문제

한 전기차 충전소에는 충전기가 일렬로 놓여 있다. 충전기에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 충전기는 현재 정상 상태이거나 고장 상태다. 관리 화면에는 정상 상태를 1로, 고장 상태를 0으로 기록한다. 충전기의 위치와 번호는 점검이 끝난 뒤에도 바뀌지 않는다. 충전소는 단체 방문 차량이 흩어져 주차하지 않도록, 번호가 연속된 충전기들로 이루어진 이용 구역을 하나 마련하려고 한다. 이용 구역에는 고장 난 충전기가 하나도 없어야 한다. 이를 위해 준비된 부품으로 고장 난 충전기를 최대 K대까지 수리할 수 있다. 고장 난 충전기 한 대를 수리하면 해당 충전기의 상태가 0에서 1로 바뀐다. 정상 충전기를 수리할 필요는 없으며, 수리를 반드시 K번 모두 할 필요도 없다. 이용 구역은 어떤 정수 l과 r에 대해 l번부터 r번까지의 모든 충전기를 포함해야 한다. 이때 1 ≤ l ≤ r ≤ N이며, 구역의 길이는 r-l+1이다. 중간에 있는 충전기를 건너뛰거나, 마지막 충전기와 첫 번째 충전기가 서로 이어진 것으로 볼 수는 없다. 이용 구역 밖에 있는 충전기의 상태는 구역을 선택하는 데 영향을 주지 않는다. 관리자는 수리할 충전기와 이용 구역을 자유롭게 선택하여 이용 구역의 길이를 최대화하려고 한다. 길이가 같은 구역이 여러 개라면 어느 구역을 선택해도 되며, 구역의 위치는 출력하지 않는다. 수리할 수 있는 고장 충전기 수가 충분하면 전체 충전기를 이용 구역으로 선택할 수 있다. 반대로 수리 이후에도 이용할 수 있는 충전기가 한 대도 없다면 구역을 만들 수 없으며, 이 경우의 답은 0이다. 충전기 상태를 나타내는 배열과 수리 가능한 최대 대수 K가 주어질 때, 만들 수 있는 이용 구역의 최대 길이를 구한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다.
둘째 줄에 각 충전기의 상태를 나타내는 정수 a₁, a₂, …, aₙ이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 100,000, 0 ≤ K ≤ N이며, 모든 aᵢ는 0 또는 1이다.

출력

수리를 최대 K대까지 진행하여 만들 수 있는 이용 구역의 최대 길이를 정수 하나로 출력한다. 구역을 만들 수 없다면 0을 출력한다.

9 1
1 0 1 1 0 1 1 1 0

6

4 0
0 0 0 0

0

5 3
0 1 0 1 0

5

출처: Devin.KR 자체 제작