题目描述

小 w 和男朋友一起养了 $n \times m$ 只猫，这些猫被排成了一个 $n \times m$ 的矩阵。

天气转凉，猫咪需要戴上帽子，帽子有黑白两种颜色。由于猫咪很傲娇，有时它们希望上下左右的相邻猫有奇数只戴着白帽子，有时希望相邻的猫有偶数只戴着白帽子。

现在猫咪们被小 w 的男朋友胡乱戴上了帽子。小 w 很头疼，于是向你求助，希望你给出一种猫咪更换帽子颜色的方案，使得猫咪们的需求能被满足，同时需要被更换帽子的猫咪尽可能少。

输入格式

从文件 matrix.in 中读入数据。

第一行三个整数 $n, m, c$ ，表示猫咪被排成了一个 $n \times m$ 的矩阵，当 $c = 0$ 时，猫满意的条件是都希望相邻的猫有偶数只戴着白帽子， $c = 1$ 时它希望相邻的猫有奇数只戴着白帽子。

接下来 $n$ 行，每行 $m$ 个数，表示矩阵中每只猫戴着帽子的颜色。 $0$ 代表黑帽子， $1$ 代表白帽子。

输出格式

输出到文件 matrix.out 中。

输出一行一个数，表示最少要给多少猫更换帽子颜色。

无解输出 $-1$ 。

3 4 1
1 1 0 1
0 1 1 0
0 0 0 1

4

数据范围与提示

对于前 $30\%$ 的数据，$n \times m \le 18$；
对于另 $20\%$ 的数据，$n = 2$；
对于 $100\%$ 的数据，$1 \le n \times m \le 300$。