方阵安排

题目描述

A 班希望在学校的行军比赛中取得一个好成绩,他们希望自己班级的行军方阵是一个完美的方阵。他们认为,如果每个人四周的男生个数为偶数,那么这就是一个完美的方阵。 现在你已知道 A 班现有的方阵,你需要把尽量少的女生改成男生,使这个方阵变成一个完美的方阵。

输入输出格式

输入格式


输入的第一行是一个正整数 $n$,表示方阵大小为 $n \times n$ 。 第 $2$ 到第 $(n+1)$ 行,每行 $n$ 个数非零即一的数字,第 $(i + 1)$ 行的第 $j$ 个数字代表方阵第 $i$ 行第 $j$ 列的人的性别,其中 $0$ 为女生,$1$ 为男生。

输出格式


输出一个数,表示最少需要把女生改成男生的个数。若无解,输出 $-1$。

输入输出样例

输入样例 #1

3
0 0 0
1 0 0
0 0 0

输出样例 #1

3

说明

#### 输入输出样例 1 解释 将方阵改为 ``` 0 1 0 1 0 1 0 1 0 ``` --- #### 数据规模与约定 对于 $40\%$ 的数据,保证 $n \leq 6$。 对于 $100\%$ 的数据,保证 $1 \leq n \leq 18$。