The optimal solution for all soldiers to reach their destinations means $X$ of them went by para-mail. This value must be the $X$ lowest removed, since the minimum amount of time we need to add is achieved when we send off the first $X$ soldiers because travelling by para-mail is slower than travelling by the Aurora.

These first $X$ soldiers would also have the maximal impact upon the times of the other soldiers (since they had to wait for them to get off) as the $i^{\text{th}}$ soldier will affect $N-(i-1)$ soldiers, and as $i$ increases, this value (and thus the maximum amount of time to be saved) strictly decreases, down to a point where it becomes zero or even negative.

After sorting the list of the destinations, we can iterate over an array containing the individual times each soldier will take and check whether it will be globally optimal to have him travel by para-mail instead. Once a soldier that would increase the total time taken if he switched to para-mail is reached, the remaining soldiers only need to be updated.

The optimal solution is the sum of all of the times in the array after this update.

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