In order to cool down, Iino devised a game she calls Whack-an-Ishigami.
In this game, she has
In one move, you can whack an Ishigami, flipping its state from up to down or vice versa (this may also cause others to flip). The goal of the game is to get all the Ishigamis down. However, Iino is having trouble, so she turns to you for help. What is the minimum number of moves you need to flip all Ishigamis down?
Constraints
There do not exist two integers
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [60%]
No additional constraints.
Input Specification
The first line contains
The next line contains
The next
Output Specification
Output one integer, the minimum number of moves required. If it is impossible to flip all the Ishigamis down without having to reset the game, output -1
.
Sample Input 1
3 3
0 1 1
3 1
1 2
3 2
Sample Output 1
2
Explanation for Sample 1
First, Iino whacks the first Ishigami, flipping the state of the first and second Ishigamis once. The states are now 1 0 1
. Then she whacks the third one, flipping the state of the first and third Ishigamis once and the state of the second Ishigami twice. The states are now 0 0 0
, and all the Ishigamis are down.
Sample Input 2
2 2
1 1
1 2
2 1
Sample Output 2
-1
Comments