农民 Byteasar 想要耕种他那块矩形的田地。他可以从田地的任意一条边开始耕种，之后每次都可以从剩余未耕种田地的任意一条边开始耕种，直到整块田地都被耕种完毕。在每次耕种完一条切片后，剩余未耕种的田地依然保持矩形形状。每条切片的宽度为 $1$，田地的长和宽分别为整数 $n$ 和 $m$。

不幸的是，Byteasar 只有一匹瘦弱的马可供耕种。一旦马开始耕种一条切片，它就不会停下来，直到该切片完全耕种完毕。然而，如果切片的负担过重，马会因劳累过度而死，因此 Byteasar 必须小心。在耕种完每一条切片后，马可以休息并恢复体力。田地不同部分的耕种难度各不相同，但 Byteasar 是一位优秀的农民，他非常了解自己的田地，因此他知道每一部分的耕种难度。

我们将田地划分为 $m \times n$ 个单位正方形，简称为方块。我们用坐标 $(i,j)$ 来标识它们，其中 $1 \le i \le m$ 且 $1 \le j \le n$。每个方块都有其耕种难度，这是一个非负整数。设 $t_{i,j}$ 表示坐标为 $(i,j)$ 的方块的难度。对于每一条切片，组成该切片的方块的耕种难度之和不能超过某个常数 $k$，否则马会死亡。

Byteasar 面临一项艰巨的任务：在耕种每一条后续切片之前，他必须决定耕种田地的哪一条边，以确保马不会死亡。另一方面，他希望耕种的切片数量尽可能少。

请编写一个程序：

• 从输入中读取数字 $k$、$m$ 和 $n$，以及耕种难度系数；
• 确定耕种 Byteasar 田地的最佳方式；
• 将结果写入输出。

输入格式

输入的第一行包含三个正整数：$k$、$m$ 和 $n$，由空格分隔，$1 \le k \le 200\,000\,000$，$1 \le m,n \le 2\,000$。接下来的 $n$ 行包含耕种难度系数。第 $j+1$ 行包含系数 $t_{1,j}, t_{2,j}, \dots, t_{m,j}$，由空格分隔，$0 \le t_{i,j} \le 100\,000$。

输出格式

你的程序应向输出写入一个整数：在满足给定条件下耕种田地所需的最少切片数量。由于我们关心动物，我们保证田地可以按照上述规则进行耕种。但请记住，拯救这匹马取决于你！

样例

输入 1

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

输出 1

8

上图展示了样例中田地的最优耕种方式。