Let's consider a single instance of Tiny completing the course for now. Let's say that there are ~NR~ targets at the ends of rows ~R[1 \dots NR]~, and ~NC~ targets at the ends of columns ~C[1 \dots NC]~, with both arrays ~R~ and ~C~ sorted in increasing order. It's easy to imagine that it's never optimal for Tiny to drive North or West – instead, he should only move South and East, hitting targets as he goes, in some order. This implies that he'll hit the ~R~ row targets in increasing order and the ~C~ column targets also in increasing order, with the only question being how they should be interleaved.

This observation suggests a naive recursive solution which tries all possible interleaved orders of targets. We should keep track of how many row and column targets Tiny has hit, and his current row and column. At each step, Tiny can either hit the next row target, if any (by driving South to its row, driving ~1~ unit East, and firing a missile), or hit the next column target, if any. This recursive process takes ~\mathcal O(2^{NR+NC})~ time, yielding an ~\mathcal O(N \times 2^N)~ solution in total.

The above algorithm can be improved with the use of dynamic programming. The recursion can be directly memoized to improve its running time to ~\mathcal O(NR \times NC \times R[NR] \times C[NC])~, which is the number of possible states (with at most two transitions from each state). This yields an ~\mathcal O(N^3 K^2)~ solution in total, where ~K~ is the largest ~P_i~ value of any target.

To achieve a dramatically more efficient solution, a different approach to the problem will be required. Before we proceed any further, we should observe that a target in column ~1~ is special in that it's the only target that can be hit without needing to rotate to face it first – as such, if there's a target in column ~1~, let's simply remove it from the ~C~ array (also decrementing ~NC~ by ~1~), and add ~1~ to the answer (as the first move in this case will clearly consist of firing a missile downwards at it).

Now, let's consider counting how many of each type of move Tiny will need to perform. Clearly, he'll fire exactly ~NR+NC~ missiles in total. Additionally, before firing at each target, he'll need to rotate to face it at some point after entering its row/column – this implies needing to drive East a minimum of ~NR~ times, and South a minimum of ~NC~ times. Besides these ~2(NR+NC)~ required moves, it's a fact that Tiny will need to drive South at least ~R[NR]-1~ times in total to reach the last row target's row (or ~0~ times if ~R = 0~), and similarly East at least ~C[NC]-1~ times in total. However, the answer can be smaller than ~2(NR+NC)+R[NR]+C[NC]-2~, because some of the ~NR+NC~ moves required for rotation can also count towards the ~R[NR]+C[NC]-2~ moves required for reaching the last row/column!

Let's assume that the final target that Tiny will hit will be in a row (we'll also want to consider the case in which he hits a column target last, and take the minimum of the two resulting answers). In this case, each of the ~NC~ times that Tiny moves South to rotate himself to hit a column target will also move him towards row ~R[NR]~. Therefore, he'll have to drive South exactly ~NC+\max(R[NR]-NC-1, 0)~ times. On the other hand, each of the ~NR~ times that Tiny moves East to rotate himself to hit a row target will also move him towards column ~C[NC]~ except for the last time (because he will already have hit the final column target by then). Therefore, he'll have to drive East exactly ~NR+\max(C[NC]-NR-2, 0)~ times.

To summarize the above thoughts, the minimum number of moves required to complete the course is ~2(NR+NC)+\min\{\max(R[NR]-NC-1, 0)+\max(C[NC]-NR-2, 0), \max(R[NR]-NC-2, 0)+\max(C[NC]-NR-1, 0)\}~, plus ~1~ if there's a target in the ~1^\text{st}~ column (which we removed from the ~C~ array). As such, as targets are added one at a time, all we need to do is maintain the values ~NR~, ~NC~, ~R[NR]~ (simply the max target row so far, initialized at ~0~), ~C[NC]~ (the max target column so far), and a flag for whether or not a target exists in the ~1^\text{st}~ column. The time complexity of this is ~\mathcal O(N)~.