Ploughing

Byteasar the farmer wants to plough his rectangular field. The field is ploughed one slice at a time. Each slice is a full strip of width $1$ taken from one of the four edges of the not-yet-ploughed region, and after every slice the remaining region is still a rectangle. This repeats until the whole field is ploughed.

Byteasar has only one weak horse. Once the horse starts a slice, it cannot stop until that slice is finished; it may rest only between slices. Each tile has a non-negative integer ploughing difficulty. The field consists of $m \times n$ unit tiles, and the tile in column $i$, row $j$ (where $1 \le i \le m$ and $1 \le j \le n$) has difficulty $t_{i,j}$. For any slice, the sum of the difficulties of its tiles must not exceed a constant $k$; otherwise the horse collapses from exhaustion, so every slice must have a difficulty sum of at most $k$.

Before each slice Byteasar chooses which edge to plough so that no slice exceeds $k$, and he wants to plough the entire field using as few slices as possible.

Write a program that reads $k$, $m$, $n$ and the difficulty coefficients, and outputs the minimum number of slices needed to plough the whole field.

The first line contains three positive integers $k$, $m$, and $n$, separated by single spaces ($1 \le k \le 2 \times 10^{8}$, $1 \le m, n \le 2000$). Each of the next $n$ lines gives the ploughing-difficulty coefficients: line $j+1$ contains $t_{1,j}, t_{2,j}, \dots, t_{m,j}$, separated by single spaces ($0 \le t_{i,j} \le 10^{5}$).

Output a single integer: the minimum number of slices needed to plough the whole field while satisfying the rule above. It is guaranteed that the field can always be ploughed.

The illustration above shows one optimal way to plough the field from the example.