Имеется сетка из
N строк и
N столбцов квадратов. Пусть (
i, j) индексы клетки, которая расположена в
i-й строке сверху и
j-м столбце слева. Эти клетки должны быть окрашены в один из цветов
C от цвета
1 до цвета
C. Первоначально (
i,
j) окрашен в цвет
ci,j. Назовем
сетку хорошей, когда выполняются следующие условия для всех
i,
j,
x,
y, удовлетворяющих
\(1<=i,j,x,y<=N\):
- если
\((i+j)\%3=(x+y)\%3\), цвет (
i,
j) и цвет (
x,
y) совпадают;
- если
\((i+j)\%3\neq(x+y)\%3\), цвет (
i,
j) и цвет (
x,
y) различны.
Здесь
\(X \% Y \) представляет
X по модулю
Y.
Мы перекрасим ноль или более клеток, чтобы сетка была хорошей сеткой.
Неправильной клеткой назовем клетку, которая имела цвет
X до перерисовки и
Y после перекраски (
DX,Y).
Найдите минимально возможную сумму всех неправильных клеток.
Входные данные
В первой строке задаются два целых числа
N и
C. В следующих
C строках задаются по
C значений
Di,j. В последних
N строках записаны
N чисел в каждой строке -
ci,j.
Выходные данные
Выведите минимально возможную сумму всех неправильных клеток
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
2 3
0 1 1
1 0 1
1 4 0
1 2
3 3 |
3 |
Перекрасить (1,1) в цвет 2. Неправильный (1,1) становится D 1,2 = 1. Перекрасить (1,2) в цвет 3. Неправильность (1,2) становится D 2,3 = 1. Перекрасить (2,2) в цвет 1. Неправильность (2,2) становится D. 3,1 = 1. В этом случае сумма неправильности всех квадратов равна 3. Отметим, что возможно \(Di, j \neq D j, i \). |
| 2 |
4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2 |
428 |
|