426. Minimum Swaps for Chessboard Transformation

0

Hard

M.S. Dhoni and Virat Kohli have a strong interest in chess. Virat presents Dhoni with a square matrix of size N × N, filled with only zeros and ones. Dhoni's task is to transform the given matrix into a chessboard configuration. To achieve this, Dhoni can perform the following operations:
• Swap any two rows of the matrix.
• Swap any two columns of the matrix.
Determine the minimum number of swaps required for Dhoni to convert the matrix into a chessboard configuration.
NOTE: In a chessboard, no adjacent elements (vertically or horizontally) are the same. Therefore, the chessboard may start with a 0 in the top-left corner.

Input Format

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

Output Format

Print the minimum number of swaps required.
If it is impossible to obtain a chessboard configuration from the given 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
Aij = 0 or 1