Let ~A_{1 \dots N}~ be the Southern skyline, and ~B_{1 \dots N}~ be the Western skyline. Let ~M_i = \min\{A_i, B_i\}~. All ~2N-1~ stacks in row ~i~ and column ~i~ must be pruned down to a height of at most ~M_i~. Let's refer to this reduction of stacks as "processing index ~i~". Note that it's not a simple matter of processing each index between ~1~ and ~N~. When an index is processed, it may affect the heights of stacks in other rows/columns, which may affect other ~A~, ~B~, and ~M~ values.

This may suggest the following approach: Process all of the indices, then process them all again, and so on until a full iteration of processing all ~N~ indices results in no further changes to the collection of coins. Processing a single index takes ~\mathcal O(N)~ time, and it can be shown that this algorithm will terminate within ~\mathcal O(N)~ iterations of processing all ~N~ indices, resulting in a time complexity of ~\mathcal O(N^3)~. Processing the indices in random orders may be tempting, but the time complexity will remain at ~\mathcal O(N^3)~, and sufficiently strong test data can be constructed such that the algorithm will require roughly ~N/2~ iterations.

A key observation is that, when an index ~i~ is processed, it can only affect the ~M~ values of other indices ~j~ when ~M_j > M_i~. Furthermore, when such an index ~j~ is affected, its ~M~ value may be reduced down to ~M_i~, but not lower than that. This suggests that, if we process all ~N~ indices in non-decreasing order of ~M~, the ~M~ values of already-processed indices will never be affected, and so a single iteration through all ~N~ indices will be sufficient.

That being said, it's insufficient to sort all ~N~ indices by their initial ~M~ values and process them in that static order, as their ~M~ values can change during the algorithm, which may change the order in which they should be processed. Therefore, we'll need to dynamically keep track of the ~A~, ~B~, and ~M~ values. At each step of the algorithm, we'll choose to process the remaining unprocessed index with the minimum ~M~ value (in a fashion reminiscent of Dijkstra's shortest path algorithm). While processing an index, we'll then need to update other ~A~, ~B~, and ~M~ values more efficiently than iterating over all ~\mathcal O(N^2)~ stacks in the grid. Overall, it's possible to implement this approach in time ~\mathcal O(N^2 \log N)~, for example by maintaining a set (balanced binary search tree) of pairs ~\{M_i, i\}~ as well as a multiset of ~C~ values for each row and each column.