밭 갈기

농부 Byteasar는 직사각형 밭을 갈려고 합니다. 밭은 폭이 $1$인 조각(slice)을 한 번에 하나씩 갈아 나갑니다. 각 조각은 아직 갈지 않은 영역의 네 변 중 한 변에서 통째로 떼어내며, 조각을 하나 갈 때마다 남은 영역은 항상 직사각형을 유지합니다. 이렇게 밭 전체를 다 갈 때까지 반복합니다.

Byteasar에게는 힘없는 말 한 마리뿐입니다. 말은 한 조각을 갈기 시작하면 그 조각을 끝낼 때까지 멈출 수 없고, 조각과 조각 사이에만 쉴 수 있습니다. 각 칸에는 음이 아닌 정수인 갈이 난이도가 매겨져 있습니다. 밭은 $m \times n$개의 단위 칸으로 이루어져 있고, 열 $i$, 행 $j$ (단, $1 \le i \le m$, $1 \le j \le n$)에 있는 칸의 난이도를 $t_{i,j}$라 합니다. 어떤 조각이든 그 조각에 포함된 칸들의 난이도 합이 상수 $k$를 넘으면 말이 지쳐 쓰러지므로, 모든 조각의 난이도 합은 $k$ 이하여야 합니다.

Byteasar는 매번 어느 변을 갈지 정해 어떤 조각도 $k$를 넘지 않도록 해야 하며, 되도록 적은 수의 조각으로 밭 전체를 갈고 싶어 합니다.

$k$, $m$, $n$과 각 칸의 난이도를 입력받아, 밭 전체를 가는 데 필요한 최소 조각 수를 구하는 프로그램을 작성하세요.

첫째 줄에 세 양의 정수 $k$, $m$, $n$이 공백 하나로 구분되어 주어집니다 ($1 \le k \le 2 \times 10^{8}$, $1 \le m, n \le 2000$). 이어지는 $n$개의 줄에 갈이 난이도가 주어집니다. $j+1$번째 줄에는 $t_{1,j}, t_{2,j}, \dots, t_{m,j}$가 공백 하나로 구분되어 주어집니다 ($0 \le t_{i,j} \le 10^{5}$).

주어진 규칙을 지키며 밭 전체를 가는 데 필요한 최소 조각 수를 정수 하나로 출력합니다. 주어지는 밭은 규칙에 맞게 항상 전부 갈 수 있음이 보장됩니다.

위 그림은 예제 입력의 밭을 가는 한 가지 최적의 방법을 보여줍니다.