You are helping plan a new stretch of highway that is M miles long. One issue that came up is the placements of gas-stations. We will assume that someone has built a gas station at the beginning (0 mile away) and at the end (M miles away) of the highway stretch. It is required that two consecutive stations (including the ones at the beginning and at the end) must be at least m0 miles apart, and at most m1 miles apart where m1 ≥ m0. You also have estimates on costs of building gas-stations at various points along the highway. The costs vary due to differences in the land around the highway, and the proximity of town. The possible options (measured from the start of the highway) are at miles x1, . . . , xn, and location xi has cost estimate ci > 0. You may assume that for the inputs you are given, there is always a feasible solution. Design a O(n log n) dynamic programming algorithm for finding a set of gas stations of minimum cost satisfying the requirements, and implement the algorithm in Java. We suggest using subproblem Opt[i] to be the minimum cost solution for the stretch of highway up to position xi with a gas-station at location xi .