Minimum Button Presses to Turn Off All Lights

You are given n lights and m buttons. Each button controls all the lights simultaneously. For the i-th button and the j-th light, pressing the button has one of the following three effects:

• If \(a_{i,j} = 1\): if the light is on, it will be turned off; if it is already off, nothing happens.
• If \(a_{i,j} = -1\): if the light is off, it will be turned on; if it is already on, nothing happens.
• If \(a_{i,j} = 0\): nothing happens to that light.

Initially, all lights are on. You can press each button at most once (pressing a button more than once does not have any extra effect). However, the order in which you press the chosen buttons may affect the final state: if a button with a \(-1\) effect on a light is pressed after a button with a \(1\) effect on the same light, it will turn that light back on.

Your task is to choose a set S of buttons and an order to press them such that the final state of every light is off. Formally, for each light \(j\) (\(0 \le j < n\)), let \(P_j = \{ i \in S \mid a_{i,j} = 1 \}\) be the buttons that can turn the light off and \(N_j = \{ i \in S \mid a_{i,j} = -1 \}\) be the buttons that might turn it on. In order to achieve the final state off, it is necessary that \(P_j \neq \emptyset\) (so that there is at least one chance to turn off light \(j\)). Moreover, in the global ordering of buttons, for each light \(j\) the first button among those in \(P_j\) must be pressed after all buttons in \(N_j\) (if any) so that the light is not reactivated.

You are to compute the minimum number of button presses needed to turn off all the lights. If there is no valid sequence of button presses that turns all the lights off, output -1.

Note: You may assume that \(m\) is small enough to allow checking all subsets of buttons.

inputFormat

The first line contains two integers n and m (\(1 \le n, m \le 20\) for example), representing the number of lights and buttons respectively.

The next m lines each contain n integers. The \(j\)-th integer in the \(i\)-th line is \(a_{i,j}\), which can be 1, -1, or 0.

outputFormat

Output a single integer: the minimum number of button presses required to turn off all the lights. If it is impossible, output -1.

sample

2 2
1 1
0 0

1