Description

Class A wants a good result in the school marching competition, and they hope their class’s marching formation is a perfect square formation. They consider the formation perfect if, for every person, the number of boys among the four adjacent neighbors (up, down, left, right) is even, considering only neighbors within the grid.

You are given Class A’s current formation. You need to change as few girls as possible into boys to make the formation perfect.

Input Format

The first line contains a positive integer $n$, meaning the formation is of size $n \times n$.

Lines $2$ to $(n+1)$ each contain $n$ numbers, each either $0$ or $1$. In the $(i+1)$-th line, the $j$-th number represents the gender of the person at row $i$, column $j$, where $0$ means girl and $1$ means boy.

Output Format

Output a single number: the minimum number of girls that need to be changed into boys. If there is no solution, output $-1$.

3
0 0 0
1 0 0
0 0 0

3

Hint

Explanation for Sample 1

Change the formation to:

0 1 0
1 0 1
0 1 0

Constraints

For $40\%$ of the testdata, $n \leq 6$.

For $100\%$ of the testdata, $1 \leq n \leq 18$.

Translated by ChatGPT 5