Maximum Regions Partition with Power‐Saving Constraint

A power company has a city modeled as an n × m grid. In the cell at row i and column j the electrical demand is an integer \(a_{i,j}\). The total demand of the city is strictly greater than the company’s supply \(u\) (i.e. \(u < \sum_{i,j}a_{i,j}\)). In order to avoid a citywide blackout, the company decides to partition the city into several contiguous rectangular regions via a series of splits. Each split is done by cutting an existing rectangular region into two sub‐rectangles along a horizontal or vertical line.

After the partition, the company will turn off the power in one region at a time (the order can be chosen arbitrarily) while supplying power to the remaining regions. In order to guarantee that the power supply is sufficient at every step, it is required that when any one region is disconnected, the total demand of the remaining regions does not exceed \(u\); equivalently, if a region with demand \(S_r\) is disconnected, then we must have \[ \text{Remaining demand} = S_{\text{total}} - S_r \le u. \] Thus every region in the partition must have a demand of at least \(S_{\text{total}} - u\>.

The company would like to:

1. Maximize the number of regions in the partition (so that each blackout affects as small an area as possible).
2. Subject to the first objective, maximize the minimum "remaining power" over all blackout events. For a given splitting step where one region (with demand \(S_a\)) is chosen to remain online and the other is cut off, the remaining power is defined as \(u - S_a\). In a complete partition strategy, the effective remaining power is the minimum of these values over all splits. (Note that when a region is never split further, it is scheduled to be turned off last and does not affect the minimum.)

Your task is to compute two values:

• The maximum number of regions that can be obtained by applying a sequence of valid splits.
• Under a partition that achieves the maximum number of regions, the maximum possible value of the minimum remaining power, i.e. the maximum over all valid partition strategies of \(\min\{u - S_a\}\) (where the minimum is taken over all split events).
• You are allowed to choose the split (horizontal or vertical) and also which resulting part will continue to be further split. However, a split is only valid if at least one of the two parts has total demand at most \(u\>.

More formally, suppose the entire grid has total demand \(S\). A valid split of a rectangle with total demand \(T\) is a division into two contiguous rectangles (via a horizontal or vertical cut) resulting in parts with sums \(S_1\) and \(S_2 = T - S_1\) such that either \(S_1 \le u\) or \(S_2 \le u\). In such a split, you choose the part with demand at most \(u\) as the active (online) area that may be split further; the other part becomes a final region. The "cost" of the split is \(S_a\) (the demand of the active area) at that step, and eventually the overall remaining power is \(u - \max(\text{all active demands along the splitting chain})\). (When splitting stops, the final region, being scheduled last, does not contribute to the cost.)

You need to design an algorithm that, given the grid and the supply \(u\), computes:

1. The maximum number of regions obtainable using a valid sequence of splits, and
2. The maximum possible minimum remaining power (i.e. \(u\) minus the maximum active demand encountered along the splitting chain) among all strategies that achieve that maximum number of regions.

Note: All formulas in this statement are typeset in \(\LaTeX\). You may assume that \(1 \le n, m \le 10\). The grid values \(a_{i,j}\) and \(u\) are positive integers.

inputFormat

The first line contains three integers \(n\), \(m\) and \(u\) (the dimensions of the grid and the power supply). Each of the next \(n\) lines contains \(m\) integers representing the grid values \(a_{i,j}\).

outputFormat

Output two numbers separated by a space: the maximum number of regions obtainable and the maximum possible minimum remaining power.

sample

1 3 5
1 2 3

3 2

</p>