28276번 - Yawned-Zoned 서브태스크

문제

정원이는 학교에서 수업을 하다가 신기한 경험을 하였다. 한 학생이 졸려서 하품을 하자 주변에 있는 학생들이 따라서 하품을 하기 시작한 것이다. 정원이가 수업하는 강의실은 $R$줄에 걸쳐 가로로 $C$개의 좌석이 격자 모양으로 배치되어 일부 칸에 학생들이 앉아있다. 한 학생이 하품을 하면 그 학생의 한 칸 앞, 한 칸 왼쪽, 한 칸 오른쪽, 한 칸 뒤쪽 자리에 앉아있는 학생이 새로 하품을 하게 된다. 이미 하품을 한 학생은 다시 하품을 하지 않는다.

학생 한 명이 하품을 하더라도 시간이 지나면 많은 학생들이 하품을 한다. 너무 많은 학생이 한 번에 하품을 하면 수업에 크게 방해되기 때문에 정원이는 세로로 칸막이를 설치하려고 한다. 칸막이는 좌석의 $i$(1ドル \leq i < C$)번째 열과 $i+1$번째 열 사이에 설치할 수 있으며 칸막이는 매우 길기 때문에 맨 앞부터 맨 뒤까지 모두 막도록 설치해야 한다.

두 학생 사이에 칸막이가 설치되어 있다면 한 학생이 하품을 하더라도 다른 학생으로 하품이 전파되지 않는다. 이 점을 이용하여 정원이는 칸막이를 $W$개 설치하여 학생 한 명의 하품했을 때 추가로 하품을 하는 학생의 수의 최댓값이 최소화되도록 하고 싶다. 정원이를 도와 칸막이를 설치하는 프로그램을 작성하여라.

입력

첫 번째 줄에 강의실의 세로 크기 $R,ドル 가로 크기 $C,ドル 칸막이의 수 $W$가 주어진다.

두 번째 줄부터 $R$개의 줄에는 강의실의 정보를 나타내는 길이 $C$의 숫자열이 주어진다. $i$번째 숫자열의 $j$번째 값은 앞에서부터 $i$번째, 왼쪽으로부터 $j$번째 좌석에 학생이 있으면 1이고 없으면 0이다.

출력

정원이가 칸막이 $W$개를 적절히 배치했을 때 한 번에 하품을 하는 학생 수의 최댓값을 출력한다.

제한

서브태스크

힌트