김일병은 생활관 복도 왁싱 작업을 진행 중이다. 일주일 후 사단장님이 방문하기 때문이다. 선진 병영이기 때문에 혼자 하는 것은 절대 아니고, 전우들이 일부 타일에 대한 왁싱 작업을 진행했기 때문에 왁싱이 안된 타일만 하면 된다.
복도의 타일은 아래 그림처럼 N행, M열 (N은 5이하의 자연수, M은 100만 이하의 자연수)로 구성되어 있다. 어느 타일은 왁싱이 이미 되어있고, 어느 타일은 왁싱이 안돼서 김일병이 해야한다. 김일병은 복도의 왼쪽에서 오른쪽으로 이동하며 왁싱을 하는데, 바로 오른쪽, 오른쪽 대각선 위, 오른쪽 대각선 아래로 이동할 수 있다. 단, 왁싱이 된 타일은 밟을 수 없다. 처음엔 그림에 있는 문 위치에서 시작한다. 왁싱은 자신의 바로 왼쪽 열에 있는 타일 중, 지금 위치에서 손에 닿는 타일에 대해서만 가능한데, 바로 왼쪽, 왼쪽 대각선 위, 왼쪽 대각선 아래 타일이 손에 닿는다.
운이 좋게도 그는 K개의(K는 10 이하의 자연수) 비닐이 있어서, 슬리퍼를 비닐로 감싸고 최대 K번은 이미 왁싱된 타일을 밟을 수 있다. 왁싱된 타일을 밟아도 왼쪽 열에 대한 왁싱은 예전과 같이 진행한다. 한 번 사용한 비닐은 버린다.
복도의 현재 왁싱 작업 상태를 담은 N * M 배열과 김일병이 지니고 있는 비닐의 수 K가 주어진다. 김일병이 왼쪽에서 오른쪽으로 이동하며 왁싱 작업을 할 수 있는 타일의 수의 최댓값을 출력하시오.
취미로 알고리즘 문제 만드는 사람