Имеется сетка из
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 |
|