Equal Sum Bipartition of a Grid

Given an ( m \times n ) grid filled with integers, determine whether it is possible to partition the grid into two connected regions such that the sum of the numbers in both regions is equal. One of the regions is required to contain the top‐left cell of the grid. If there are multiple valid partitions, output the minimum number of cells in the region that contains the top‐left cell. If no valid partition exists, output 0.

A region is defined as a set of grid cells that are connected vertically or horizontally. The partition divides the grid in such a way that every cell belongs to exactly one of the two regions and both regions are non‐empty.

The equality condition for the partition requires that [ \text{sum}(\text{region A}) = \text{sum}(\text{region B}) = \frac{\text{total sum}}{2}. ]

Both regions must be connected. Since the region containing the top‐left cell is predetermined, you are asked to find such a connected subset (starting from the top‐left cell) whose sum equals half of the total sum, and moreover, that the remaining cells also form a connected region. In case of multiple answers, report the one with the smallest number of cells in the top‐left region.

inputFormat

The input starts with two integers ( m ) and ( n ) (the number of rows and columns of the grid). This is followed by ( m ) lines, each containing ( n ) integers, representing the grid.

outputFormat

Output a single integer: the minimum number of cells in the region that contains the top‐left cell for which a valid equal-sum bipartition exists. If no partition exists, output 0.

sample

2 2
1 3
2 4

0