Description

Xiao Z found a job at a power supply company and immediately encountered a tricky task.

The city where Xiao Z works can be modeled as an $n \times m$ grid. The cell in row $i$ and column $j$ has a power demand $a_{i,j}$. However, the available supply $u$ from the company is less than the sum of the demands of all cells. Therefore, the company has to partition the city into several regions and rotate power outages across these regions, so that after cutting power to any one region, the sum of the demands of the remaining regions does not exceed the available supply.

For convenience, the partitioning is performed as follows: at each step, a (rectangular) region is split horizontally or vertically into two smaller (rectangular) regions, recursively.

To minimize public dissatisfaction, the company asks Xiao Z to compute:

• the maximum possible number of regions, and
• subject to achieving that maximum number of regions, the maximum possible remaining power, where for a given partition, its remaining power is defined as the minimum, over all outages, of $u$ minus the total demand of the regions that remain powered.

Input Format

The first line contains three integers $n, m, u$.

The next $n$ lines each contain $m$ integers. On the $i$-th line, the $j$-th integer is $a_{i,j}$, as defined above.

Output Format

Output one line containing two integers: the maximum number of regions and, subject to that, the maximum remaining power.

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

Hint

Constraints:

• For $60\%$ of the testdata, $1 \leq n, m \leq 10$.
• For $100\%$ of the testdata, $1 \leq n, m \leq 32$, $1 \leq a_{i,j} \leq 100$.

Translated by ChatGPT 5