题目描述

A 班希望在学校的行军比赛中取得一个好成绩，他们希望自己班级的行军方阵是一个完美的方阵。他们认为，如果每个人四周的男生个数为偶数，那么这就是一个完美的方阵。

现在你已知道 A 班现有的方阵，你需要把尽量少的女生改成男生，使这个方阵变成一个完美的方阵。

输入格式

输入的第一行是一个正整数 $n$，表示方阵大小为 $n \times n$ 。

第 $2$ 到第 $(n+1)$ 行，每行 $n$ 个数非零即一的数字，第 $(i + 1)$ 行的第 $j$ 个数字代表方阵第 $i$ 行第 $j$ 列的人的性别，其中 $0$ 为女生，$1$ 为男生。

输出格式

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

3
0 0 0
1 0 0
0 0 0

3

提示

输入输出样例 1 解释

将方阵改为

0 1 0
1 0 1
0 1 0

数据规模与约定

对于 $40\%$ 的数据，保证 $n \leq 6$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 18$。