Road trip suppose you want to drive from san francisco to new york city on i-80. your car holds c gallons of gas and gets m miles to the gallon. you are handed a list of the n gas stations that are on i-80 and the price that they sell gas. let di be the distance of the i th gas station from sf, and let ci be the cost of gasoline at the i th station. furthermore, you can assume that for any two stations i and j, the distance |di − dj | between them is divisible by m. you start out with an empty tank at station 1. your final destination is gas station n. you may not run out of gas between stations but you need not fill up when you stop at a station, for example, you might to decide to purchase only 1 gallon at a given station. find a polynomial-time dynamic programming algorithm to output the minimum gas bill to cross the country.