Description

Byteasar, the farmer, wants to plough his rectangular field. He can begin by ploughing a slice from any of the field’s edges; then he can plough a slice from any edge of the remaining unploughed field, and so on, until the whole field is ploughed. After each slice is ploughed, the yet-unploughed field is still a rectangle. Each slice has a span of $1$, and the field is divided into $m\times n$ unit tiles.

We identify the tiles by their coordinates $(i,j)$, for $1\le i\le m$ and $1\le j\le n$. Each tile has a non-negative ploughing-difficulty. Let $t_{i,j}$ denote the difficulty of the tile with coordinates $(i,j)$.

Byteasar has only one puny and frail nag (horse). Once the nag starts to plough a slice, it will not stop until the slice is completely ploughed. However, if the slice is too much for the nag to bear, it will die of exhaustion, so Byteasar has to be careful. After every ploughed slice, the nag can rest and gather strength. For every slice, the sum of ploughing-difficulties of the tiles forming it cannot exceed a certain constant $k$.

Determine the minimum number of slices required to plough the entire field without exceeding the limit $k$ on any slice. It is guaranteed that there exists a way to plough the field according to the above rules.

Input Format

• The first line contains three positive integers $k$, $m$ and $n$, separated by single spaces, where $1\le k\le 200\ 000\ 000$ and $1\le m,n\le 2000$.
• The next $m$ lines contain the ploughing-difficulty coefficients. Specifically, line $i+1$ ($1\le i\le m$) contains $n$ integers $t_{i,1}, t_{i,2}, \ldots, t_{i,n}$, separated by single spaces, where $0\le t_{i,j}\le 100\ 000$.

Output Format

Output one integer: the minimum number of slices required to plough the field while satisfying the given conditions. It is guaranteed that a valid ploughing exists.

12 6 4
6 0 4 8 0 5
0 4 5 4 6 0
0 5 6 5 6 0
5 4 0 0 5 4

8

Hint

Thanks to @NaVi_Awson for the translation.

Translated by ChatGPT 5