Why can't we view submission in gym? Does someone know the reason? If we can, then this problem will be solved, too.

You can write MxN equations R[i] + C[j] = K — A[i][j] (mod K), where R[i] — number of operation "increment i-th row", C[j] — number of operations "increment i-th column".

Now let's R[i] = 0. With that you can calculate all C[j] and R[i]. And total number of operations is sum of all R[i] and C[j].

It is one of the possible answers, but can be not minimal. It's because R[0] from optimal answer can be not 0.

We can't brute all values of R[0]. But we can do next observation: if we increment any of R[i] — we need to increment all R[i] and decrement all C[j]. When we do this, total number of operation will be changed for M — N.

It can be easy proven, that optimal answer would contain some R[i] or C[j] equals to 0 (if not — we can decrement our answer for M — N or N — M at most once).

So we can simply iterate over all R[i] and C[j], set it to 0 and find answer for that setting. From all answers we need to choose answer with minimal sum of operations.

P.S. Can you modify this from O((N+M)^2) to O((N+M)log(N+M))? ;)