方阵安排

题目描述

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

输入输出格式

输入格式


第1行,一个正整数n,表示方阵大小为n\*n的。 第2~n+1行,每行n个数,代表方阵中的人(0为女生,1为男生)。

输出格式


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

输入输出样例

输入样例 #1

3
0 0 0
1 0 0
0 0 0

输出样例 #1

3

说明

对样例的说明: 将方阵改为:0 1 0 1 0 1 0 1 0 即可。 数据范围: 对于40%的数据,n≤6 对于100%的数据,n≤18