Let us consider having a pair \((X, Y)\) as placing a piece at a square \((X, Y)\) to rephrase the problem to one about placing pieces on a two-dimensional grid.

Assume \(N \le M\) without loss of generality.

Since the minimum and maximum values for \(3X_i + Y_i\) are \(4\) and \(3N+M\), respectively, we see that \(3N+M-3\) is an upperbound for \(K\). We claim that this upperbound is achievable except when \(N = M\) and \(N\) is even.

For now, we exclude the case \(N = M\) and \(N\) is even. Here is an optimal placement:

oooxxxxxxxxxxxx
oooxxxxxxxxxxxx
oooooxxxxxxxxxx
xxoooxxxxxxxxxx
xxoooooxxxxxxxx
xxxxoooxxxxxxxx
xxxxooooooooooo

\(3X+Y\) increases by \(1\) each time we move as follows:

• go from \((i,j)\) to \((i,j+1)\);
• go from \((i,j)\) to \((i+1,j-2)\).

Using these two moves, it is possible to reach \((N, M)\) from \((1,1)\) passing all o’s and no other squares, which proves that all o’s have different values of \(3X+Y\) and that there are \(3N+M-3\) o’s. For \(X+3Y\), again, we can similarly prove that all o’s have different values of \(X+3Y\), though we go out of the grid during the process.

For the case \(N = M\) and \(N\) is even, an optimal placement can be constructed similarly, too:

oooxxx
oooxxx
ooooox
xxooox
xxoooo
xxxxoo

However, as shown above, the square \((N-1,N+1)\) does not exist, so we can have one less o while going \((N-1,N) \rightarrow (N-1,N+1) \rightarrow (N,N-1)\).

Below, we prove that the optimal solution is \(3N+M-4\).

When \(N=2\), we can place pieces on all squares to have the optimal solution \(3N+M-4 = NM\).

Consider the case \(N \ge 4\). Let \(S\) be the set of squares in the grid reachable from \((3,1)\) by the following two moves. Here, it is allowed to go out of the grid temporarily.

• Go from \((i,j)\) to \((i+1,j-3)\).
• Go from \((i,j)\) to \((i+3,j-1)\).

The elements of \(S\) have \(\frac{N}{2}\) different values of \(3X+Y\), and \(\frac{N}{2}-1\) different values of \(3X+Y\), so we have \(3N+M-4\) as another upperbound for \(K\), improved by \(1\) from \(3N+M-3\).

Thus, we have solved the problem in \(\mathrm{O}(N+M)\) time.

Special thanks to maspy for the unusual amount of help during the preparation of this problem.