819. Swaps To ChessBoard

0

Hard

M.S. Dhoni and Virat Kohli have a strong interest in chess. Virat presents Dhoni with an N x N array filled with only zeroes and ones. Dhoni's task is to transform the given array into a chessboard. To achieve this, Dhoni can perform the following operations:

- Swap any two
**rows** - Swap any two
**columns**

**NOTE:**In a**ChessBoard**, no adjacent elements (vertically or horizontally) are the same. Therefore, the board may start with a 0 in the top-left corner.Input Format

The first line contains an integer N.
The next N lines contain N space-separated 0's or 1's, representing the matrix.

Output Format

Print the minimum number of swaps required.

*If it is impossible to obtain a chessboard from the matrix, print -1.*Example

Input

4
0 1 1 0
0 1 1 0
1 0 0 1
1 0 0 1

Output

2

Constraints

2 <= N <= 30

A

A

_{ij}= 0 or 1Loading...

View Submissions

Console