[AdditionalFile5503.zip](file://AdditionalFile5503.zip?type=additional_file)

#5503. 「POI2006 R2」耕作 Ploughing

标签: 传统 | 时间限制: 4000 ms | 内存限制: 64 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – II etap Orka

农夫 Bajtazar 想要耕作一块矩形的田地。Bajtazar 可以从田地的任意一边开始犁第一道垄，然后从剩下未耕作部分的任意一边再犁一道垄，如此往复，直到整块田地都被耕作为止。每犁完一道垄后，未耕作的部分仍然是一个矩形。每道垄的宽度为 $1$，田地的长度和宽度分别为整数 $m$ 和 $n$。

不幸的是，Bajtazar 只有一匹体弱的瘦马用来耕地。当这匹马开始犁一道垄时，它会一直犁到头，不会中途停下。Bajtazar 必须小心，如果犁一道垄对这匹马来说太过费力，马就会倒下。每犁完一道垄，马都可以休息并恢复体力。田地里并非所有地方的耕作难度都一样。Bajtazar 非常了解他的田地，并且确切地知道每个位置的耕作难度。

我们将这块田地划分为 $m \times n$ 个单位正方形。我们将用坐标 $(i, j)$ 来标识这些正方形，其中 $1 \le i \le m$ 且 $1 \le j \le n$。每个正方形都被赋予了一个非负整数的耕作难度系数。坐标为 $(i, j)$ 的正方形的耕作难度系数我们记为 $t_{i, j}$。对于任何一道垄，构成这道垄的所有正方形的耕作难度系数之和都不能超过一个给定的常数 $k$，否则马就会倒下。

Bajtazar 面临着一个艰巨的任务。在犁每一道垄之前，他都必须决定从当前未耕作部分的哪一边开始，以确保马不会倒下。另一方面，他也希望犁出的垄数尽可能少。

请编写一个程序，实现以下功能：

• 从标准输入读取数字 $k, m$ 和 $n$，以及各个位置的耕作难度系数，
• 确定 Bajtazar 应该如何耕作这块田地，
• 将结果输出到标准输出。

输入格式

输入的第一行包含三个正整数：$k, m$ 和 $n$ $(1 \le k \le 200000000, 1 \le m \le 2000, 1 \le n \le 2000)$，由单个空格隔开。

接下来的 $n$ 行是耕作难度系数。第 $j+1$ 行包含系数 $t_{1, j}, t_{2, j}, \ldots, t_{m, j}$ $(0 \le t_{i, j} \le 100000)$，由单个空格隔开。

输出格式

你的程序应向标准输出输出一个整数，表示在满足给定条件下，耕作整块田地所需的最少垄数。你可以假设，对于给定的输入数据，总是存在一种满足题目条件的耕作方案。

样例

输入

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

上图展示了一种可行的田地耕作方式样例。