Choosing \(R\) that does not correspond to any of the \(y\) coordinates of the given \(N\) square does not improve the answer, and same applies to \(C\) and \(x\); so one can do coordinate compression and regard the problem on a \(N\)-by-\(N\) (or less) grid.

For a given \((R,C)\), \(S\) equals “(the sum of integers written in the \(R\)-th row) \(+\) (the sum of integers written in the \(C\)-th column) \(-\) (the integer written on \((R,C)\)).” We this in mind, we search for \(R\) exhaustively. We can basically choose \(C\) that maximizes the sum of integers written in the \(C\)-th column. Especially, if \((R,C)\) is not in the input, choosing a column that does not maximize the sum does not improve \(S\). If \((R,C)\) is in the input, this is not always the case, so we should inspect the second one. If \((R,C)\) for that \(C\) is still contained in the input, we should see the third, \(\ldots\), and so on. However, whenever \((R,C)\) is not in the input, choosing a column with the sum less than that does not improve \(S\), so you can stop there. This iteration until stopping is repeated at most \(\mathrm{O}(N)\) in total over \(R=1,2,\ldots,N\), so the algorithm above finds the answer fast enough.