Description

There are $n$ lamps and $m$ buttons. Each button can control all $n$ lamps simultaneously — pressing the $i$-th button affects every lamp. For lamp $j$, pressing button $i$ has one of the following three effects:

• If $a_{i,j} = 1$, then if this lamp is on, turn it off; otherwise do nothing.
• If $a_{i,j} = -1$, then if this lamp is off, turn it on; otherwise do nothing.
• If $a_{i,j} = 0$, do nothing regardless of the lamp’s state.

All lamps are initially on. Given the effects of every button on every lamp, find the minimum number of button presses needed to turn all lamps off.

Input Format

The first line contains the integer $n$.
The second line contains the integer $m$.

The next $m$ lines each contain $n$ integers. On line $i + 2$, the $j$-th integer is $a_{i,j}$, representing the effect of button $i$ on lamp $j$.

Output Format

Output a single integer — the minimum number of button presses. If it is impossible to turn all lamps off, output $-1$.

3
2
1 0 1
-1 1 0

2

Hint

Constraints

• For $20\%$ of the testdata, printing “no solution” can score points.
• For $20\%$ of the testdata, $n \le 5$.
• For $20\%$ of the testdata, $m \le 20$.

The above test points may overlap.

For $100\%$ of the testdata, $1 \le n \le 10$, $1 \le m \le 100$.

Translated by ChatGPT 5