Description

As shown in Figure $1$, some integers are filled in a $3\times 3$ grid.

We cut along the red line in the figure and get two parts, and the sum of the numbers in each part is $60$.

Your task is to write a program to determine: for the given integers in an $m\times n$ grid, whether it can be divided into two parts such that the sums of the numbers in the two regions are equal.

If there are multiple solutions, output the minimum number of cells in the region that contains the top-left cell.

If it cannot be divided, output $0$.

Input Format

The program first reads two integers $m$, $n$, separated by spaces $(m,n<10)$, representing the width and height of the grid.

Next are $n$ lines, each containing $m$ positive integers separated by spaces. Each integer is at most $10000$.

Output Format

Output: among all solutions, the minimum possible number of cells in the partition region that contains the top-left cell.

3 3
10 1 52
20 30 1
1 2 3

3

4 3
1 1 1 1
1 30 80 2
1 1 1 100

10

Hint

In the second example:

Time limit: 5 seconds, 64 MB. Lanqiao Cup 2013, the 4th Provincial Contest.

Translated by ChatGPT 5