A native Australian named Anatjari wishes to cross a desert carrying only one single water bottle. There are n watering holes along the way and he has a map that marks all of them. The only places allowing him to rell his bottle are at these watering holes, but he can select which of the watering holes to stop at. He starts from location s with one bottle of water, and he needs to walk miles from s to watering hole , for i = 1, 2,..., n . Suppose he can walk at most M miles on one bottle of water, and if he only walks x . We say Anatjari will nally cross the desert by arriving at the last watering hole . Design an efficient algorithm in pseudocode, using dynamic programming, to determine which watering holes Anatjari should stop at and refill his bottle in order to cross the desert and minimize his total \wasting". Prove the correctness of your algorithm.

h1, h2...hn