First, we will make the observation that we don't have to actually insert the ~M~ pies before we start choosing — it's more convenient to keep a "bag of pies" that we can insert in the line at any point in time as we are walking along the line.

With the exception of at most one pie, all of the pies in the bag will either be used as separators between two taken pies or we will take them for the sugar. Suppose we take ~K~ pies from the bag in the optimal solution for the sugar. It's obvious that these will be the ~K~ pies with the highest sugar content. And the pies that we use as separators should be the pies with the lowest sugar, since wasting any other pie would result in a potentially worse solution.

With these observations, we can sort the ~M~ pies in nondecreasing order. Since we will only be using either the least sugary pie or the most sugary pie each time we choose to insert a pie in the line, at any point in time the pies in our bag must be from a continuous subarray of the original sorted array.

Now, we analyze the possible cases as we walk along the line of ~N~ pies.

• Case 1: We can take the pie from the line, assuming we didn't take the previous pie.
• Case 2: We can skip this pie.
• Case 3: If we have taken the previous pie, we can insert a spare pie from the bag to use as a separator.
• Case 4: We can take a spare pie, assuming we didn't take the pie before.
• Case 5: We are at the end of the line, and we have spare pies left.
  • Case 5a: We didn't take the previous pie, so we can take the spare pie with the highest sugar content.
  • Case 5b: We took the previous pie, so we must use a spare pie as a separator.

Combining all of these cases will give a recursive solution.

The optimal solution depends on which of the ~N~ ordered pies we are currently looking at, whether we've taken the previous pie (this can be either a pie from the ~N~ pies or a pie we inserted from the ~M~ pies, and it determines whether we can take the current pie), and which pies are left in our bag.

If we haven't taken the previous pie, we can choose to take this pie, we can take a pie from the bag (assume we inserted it right before the current pie), or we can choose to skip this pie. The latter case can be handled by recurring to almost the same state, but assuming we took the previous pie, since that will force us not to take the current pie.

If we took the previous pie, we can either skip this pie or we can insert a spare pie right before this.

If we're at the end of the line, our only choice is to use the spare pies until we run out. Whether we can take the pie with the most sugar or we need to "waste" a pie depends entirely on whether the previous pie was taken.

As with most recursive solutions with a finite number of different states, we can memoize it (cache the answers) to turn it into a dynamic programming solution.

Time Complexity: ~\mathcal{O}(M \log M + NM^2)~