题目描述

Byteasar 想耕种他那块矩形的田，他每次能耕种矩形的一边（上下左右都行），在他每次耕完后，剩下的田也一定是矩形，每块小区域边长为 $1$，耕地的长宽分别为 $m$ 和 $n$，不幸的是 Byteasar 只有一匹老弱的马，从马开始耕地开始，只有当它耕完了一边才会停下休息。但有些地会非常难耕以至于马会非常的累，因此 Byteasar 需要特别小心。当耕完了一边之后，马可以停下来休息恢复体力。每块地耕种的难度不一，但是 Byteasar 都非常清楚。我们将地分成 $m\times n$ 块单位矩形——我们用坐标 $(i,j)$ 来定义它们。每块地都有一个整数 $t_{i,j}$,来定义 $(i,j)$ 的耕种难度。所以每次马耕一边地时的难度就是所有它耕种的地的难度总和，对于这匹虚弱的马而言，这个值不能超过他的体力值。Byteasar 想知道在马不死掉的情况下最少需要耕多少次才能把地耕完。

输入格式

第一行三个整数：$k, m, n$
接下来 $n$ 行 $m$ 列表示 $t$。

输出格式

输出马不死掉的情况下最少需要耕多少次才能把地耕完。

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

提示

感谢 @NaVi_Awson 提供翻译

$0\le t_{i,j}\le 100\ 000,1\le k\le 2\times 10^8,1\le m,n\le 2000$。