When a bomb is placed to \((A, B)\), then the targets to destroy on the \(A\)-th or the \(B\)-th column can be destroyed. Therefore, let \(R_A\) be the number of bombs in the \(A\)-th row, and \(C_B\) be the number of bombs in the \(B\)-th column, then the number of bombs that will explode will be about \(R_A + C_B\).

Since only \(R_A\) is dependent on \(A\) and only \(C_B\) is dependent on \(B\), it may seem that \(A\) and \(B\) can be determined independently, but the problem is that the number of bombs that explodes is not always \(R_A + C_B\).

If a target to destroy exists on the coordinates \((A, B)\), \(1\) is added to both \(R_A\) and \(C_B\), but there is only one target to destroy, so the actual number of targets to destroy will be \(R_A + C_B - 1\). Therefore, after finding the maximum value for \(A\) and \(B\) independently, it has to be checked whether there exists a pair \((A, B)\) such that both \(R_A\) and \(C_B\) is maximum and there is not a target to destroy on the coordinates \((A, B)\). While the number of \((A, B)\) may be very large, there are at most \(M\) squares that targets to destroy exist, so the number of searches can be kept down to no more than \(M\) times, which is small enough to do brute-force search.

If such pair exists, then the answer is \(\max(R) + \max(C)\), otherwise the answer is \(\max(R) + \max(C) - 1\).

Sample Code(TODO)