题目描述

小Z在供电公司找到了一份工作，刚上班就遇到了一个棘手的任务。

小Z所在的城市可以看成一个 n*m 的网格，第 i 行第 j 列的格子有电力需求 a[i][j] 。然而，供电公司能够供应的电力 u 小于每格的电力需求之和。为此，供电公司不得不将城市划分成若干个区域，每个区域轮流断电，使得断电后剩余区域的电力需求之和不超过供电公司能够供应的电力。

为了方便起见，划分区域的方式很简单，每次将大区域横向或纵向划分成两个小区域，递归进行。

供电公司想尽可能减少市民的不满，因此需要小Z计算出最多能划分成多少个区域以及在此前提下能够剩余的最多电力（一种划分的剩余电力为每次断电后剩余电力的最小值），希望你帮帮他。

输入格式

第一行包含三个整数 n，m，u。

接下来 n 行，每行包含 m 个整数，第 i 行第 j 个整数为 a[i][j] 。

输出格式

第一行包含两个整数，表示最多能划分成的区域数和在此前提下能够剩余的最多电力。

3 3 33
4 4 2
2 9 6
6 5 3

4 1

3 4 15
1 2 1 2
2 1 2 1
1 2 1 2

6 0

提示

【数据规模】

对于 60% 的数据，n，m ≤ 10。

对于 100% 的数据，1 ≤ n，m ≤ 32，1 ≤ a[i][j] ≤ 100。