410325: GYM104009 I Matrix

Andrei is very keen on Physics, but he really hates maths. He always says: "Arghh, maths is just a tool, I don't need to understand it. It just helps me to do Physics!". Also, Andrei likes Computer Science and got stuck with the following problem:

You are given a matrix of size $$$N * M$$$ full of numbers modulo $$$3$$$. You can change any number in the matrix with another value modulo $$$3$$$. This operation has a cost equal to the absolute difference between the new value and the old one. The cost to change more elements is the sum of the costs to change each element individually. A submatrix of the initial matrix is called "special" if the number of rows is divisible by $$$2$$$ and the number of columns is divisible by $$$3$$$. Can you change the given matrix so that the sum inside each "special" submatrix is $$$1$$$ modulo $$$3$$$? If yes, what would be the minimum cost?

Please help Andrei to solve this problem even if you don't agree with his strong opinions!

The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 1000$$$) and $$$M$$$ ($$$1 \leq M \leq 1000$$$), denoting the number of rows and columns of the given matrix $$$A$$$.

Each of the following $$$N$$$ lines contains $$$M$$$ positive integers, denoting the values of the matrix $$$A$$$ ($$$0 \leq A_{i,j} \leq 2$$$).

On a single line, print the minimum cost to transform the matrix $$$A$$$ or $$$-1$$$ if it is not possible.

2 3
0 0 0
0 0 2

1