Let's start off by adding the number 0 to our list of integer coordinates. This is the starting coordinate and we will treat it as a dew drop. Now consider the list ~pos~ as the sorted list of integer coordinates and say ~N~ is the size of our new list.

The approach begins with the observation that the drops of dew the beetle will drink in the most optimal solution will always be a continuous segment of our list. Because it takes no time for the beetle to drink a drop of dew, drinking a drop of dew at position ~x~ means the beetle should drink all the drops en route from ~0~ to ~x~ in order to maximize the amount of water drank.

Given this, we define ~f(i, j, k)~ to be the lowest cost to drink ~k~ drops of dew after drinking all the water from the range ~(i, j)~. Note this value does not include the cost to drink the drops in the range ~(i, j)~. The lowest cost is defined as the cumulative water lost across all ~k~ drops of dew.

However, ~f(i, j, k)~ does not account for the position of the beetle at this state (it may be at position ~i~ or ~j~). Thus, we define ~L(i, j, k)~ to be ~f(i, j, k)~ with the beetle at position ~i~, while ~R(i, j, k)~ is to be ~f(i, j, k)~ with the beetle at position ~j~.

The base case is ~f(i, j, 0) = 0~, as it takes ~0~ cost to drink ~0~ drops of dew.

The transition is then ~L(i, j, k) = min(L(i-1, j, k-1) + c1, R(i, j+1, k-1) + c2)~. ~c1~ is the cost required to get from ~i-1~ to ~i~, and can be found through the formula ~c1 = k(pos[i]-pos[i-1])~. This is due to each of the ~k~ drops of dew losing a unit of water for each unit of distance travelled. ~c2~ uses the same formula but with the points ~i~ and ~j+1~.

Likewise, ~R(i, j, k) = min(L(i-1, j, k-1) + c1, R(i, j+1, k-1) + c2)~, where ~c1~ involves the points ~i-1~ and ~j~, and ~c2~ involves the points ~j~ and ~j+1~.

The final answer can be found by taking the maximum over all ~kM - L(s, s, k)~, where ~s~ is the index of 0 in ~pos~, and ~0 \le k \le N~. This works because the range defined in ~L~ is ~(s, s)~, which means we consider ~s~ as already drunk before the bug drinks ~k~ more drops. The formula itself subtracts the cumulative water lost across all ~k~ drops of dew (see paragraph 3) from the total water initially available: ~kM~.