If the sum of \(A\) and that of \(B\) are different modulo \(K\), the objective is obviously unachievable. Below, we consider the other case.

Let us start by hypothetically writing \(K-1\) in every square, and try to fit the conditions by decreasing the numbers.

For each row and each column, we can find the amount by which we need to reduce the sum modulo \(K\). Let \(C_i\) and \(D_i\) be those amounts.

Let \(Z=\max(\sum_{1 \leq i \leq H} C_i, \sum_{1 \leq i \leq W} D_i)\). We have to decrease the numbers by at least \(Z\) in total.

On the other hand, we can show the existence of a solution where we decrease the numbers by exactly \(Z\) in total. Therefore, the answer is \(HW(K-1)-Z\). Below, we will show the existence of such a solution.

Because \(\sum_{1 \leq i \leq H} C_i \equiv \sum_{1 \leq i \leq W} D_i \bmod K\), it is possible to add some multiple of \(K\) to \(C_1\) or \(D_1\) so that \(\sum_{1 \leq i \leq H} C_i = \sum_{1 \leq i \leq W} D_i = Z\).

Now, repeat the following \(Z\) times.

• Find \(i,j\) such that \(C_i \geq 1,D_j \geq 1\). Decrease by \(1\) the value at the \(i\)-th row and \(j\)-th column, and also \(C_i\) and \(D_j\).

Here, the value at the \(i\)-th row and \(j\)-th column will be decremented at most \(\min(C_i, D_j) \leq K-1\) times, so there will never be a negative value. This completes the proof.

Sample Solution (pypy3)