We claim that ~\max(R+1, C+1) + 1~ is always achievable.

Let's imagine a grid with ~R = 3~ and ~C = 3~ and trains placed wherever possible.

Assume that cell ~(0,0)~ is the top-leftmost cell and cell ~(R+1, C+1)~ is the bottom-rightmost cell. The number in each cell denotes the time that each train in the leftmost column (first diagram) or topmost row (second diagram) will arrive, mod ~2~. Departure times are scheduled based using the following algorithm:

Assign each train on the leftmost column to depart at time ~a_i \bmod 2~ and each train on the topmost row to depart at time ~(b_i + 1) \bmod 2~.

The following diagrams provide a visualization:

It is clear that for all trains departing from the leftmost column, the parity of the arrival time at any cell ~(i, j)~ will form a checkerboard of ~1~'s and ~0~'s across the entire grid. This also holds for the trains departing from the topmost row. This checkerboard pattern can be extended or shrunk to fit any ~R~ and ~C~.

Call the checkerboard formed with the trains departing from the leftmost column ~A~ and the checkerboard formed with the trains departing from the topmost row ~B~. We can see that for any cell ~(i, j)~, ~A_{i, j} \ne B_{i, j}~. Therefore, any collision among trains departing from the leftmost column and trains departing from the topmost row is impossible.

We conclude that we can always achieve an answer of ~\max(R+1, C+1) + 1~.

Now, we attempt to achieve a ~\max(R+1, C+1)~ solution.

Assume without loss of generality that ~R \le C~.

We can observe that each train on the leftmost column will have to depart at time ~0~, or else they will arrive later than ~\max(R+1, C+1)~. Define the difference as ~D = C-R~. Now we can see that every train on the topmost row ~b_i~ needs to leave in the interval ~[0, D]~ inclusive or else it will not reach the end of its row in time. Therefore, it suffices to check if there is any row ~x~ between rows ~[b_i - D, b_i]~ inclusive such that for all ~a_j~ ~(1 \le j \le N)~, ~a_j \ne x~.

This can be done using line sweep or efficient binary search/preprocessing methods. If during this calculation we find that there are no cells that meet the above criteria, the solution for the scenario must be ~\max(R+1, C+1) + 1~.

Time Complexity: ~\mathcal{O}(N + M)~ or ~\mathcal{O}(N + M \log N)~

Additional Notes

The checker for this problem was included in the problemset as An Animal Contest 3 P4 - Monkey Mayhem.