Ploughing the Field

Byteasar, the farmer, needs to plough his rectangular field without fatiguing his weak nag. The field is divided into (m \times n) unit square tiles with coordinates ((i,j)) for (1 \leq i \leq m) and (1 \leq j \leq n). Each tile has a non-negative integer ploughing-difficulty (t_{i,j}). At every move, Byteasar can choose one of the four edges of the current rectangular unploughed field and plough a slice (a full row or a full column) of span (1). However, the sum of the difficulties of the tiles in the chosen slice must not exceed a given constant (k); otherwise, his nag will die of exhaustion. Note that once a slice is being ploughed, the nag works through it without stopping, though he can rest between slices. After each slice, the remaining unploughed field remains rectangular.

Byteasar wishes to complete the ploughing using as few slices as possible while keeping each slice's total difficulty at most (k). Your task is to determine the minimum number of slices required to plough the entire field. If it is impossible to plough the field without exceeding the nag's strength, output (-1).

The process can be described recursively. Let (f(r_1, r_2, c_1, c_2)) be the minimum number of slices needed to plough the submatrix of tiles from row (r_1) to (r_2) and column (c_1) to (c_2). At each step, you may remove the top row, bottom row, left column, or right column if the sum of difficulties in that row or column (over the current submatrix) is at most (k). The answer for the entire field is (f(1, m, 1, n)).

inputFormat

The first line contains three integers: (k), (m), and (n) -- the maximum difficulty the nag can handle in one slice, the number of rows, and the number of columns respectively. The next (m) lines each contain (n) non-negative integers. The (j)-th number in the (i)-th line is (t_{i,j}), the ploughing-difficulty of the tile at position ((i,j)).

outputFormat

Output a single integer: the minimum number of slices required to plough the entire field without exceeding the difficulty threshold on any slice. If it is impossible to plough the entire field under the given conditions, output (-1).

sample

5 1 1
5

1