Background

This problem does not guarantee that there exists a solution that works for any input within the Constraints of this problem. Because the testdata is too weak, a program that passes this problem may not be completely correct (wrong time complexity, or correctness not guaranteed). The statement and testdata are for reference only. This problem does not accept adding hack data.

This problem is incorrect. It is not recommended to try or submit this problem. Details about this type of problem

The 3 test points in Subtask 0 are from the Lanqiao Cup testdata.

Problem 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