Note that any collision between any pair of monkeys is going to be at a single, distinct cell at only one possible moment in time. If the monkey on the leftmost column is at row $i$ (call this monkey $a$) and the monkey on the topmost column is at row $j$ (call this monkey $b$), the point of collision will be at cell $(i,j)$.

If monkey $a$ leaves at time $x$, monkey $b$ will need to leave at time $x+j-i$. If we represent monkey $b$'s departure time as $y$ then we get the equation $y=x+j-i\Rightarrow y+i=x+j$. Swap $i$ and $j$ and we get $y-j=x-i$. Now these values $y-j$ and $x-i$ can easily be calculated through iteration over the departure times for monkeys on the topmost row and leftmost column.

We can then observe that over all distinct values of $y-j$, we add to our answer the minimum between the number of occurrences of $y-j$ and the number of occurrences of $x-i$ such that $y-j=x-i$. This is because each $y-j$ must be paired with an $x-i$ to achieve a collision, extras will not collide with any other monkey.

Implementation can be done using a map to count occurrences, resulting in a log factor. There is also another solution involving sorting.

Time Complexity: $\mathcal{O}((N+M)\cdot \log (N+M))$

Additional Notes

Big thanks to 4fecta for suggesting this problem.