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.