Lorenzo is going on another trip! This time, he$$s

back to his gasoline$-$powered car. He has already figured out the path he is going to take, and knows that there are gas

stations g$1,...,$ gn along the path $($in that order$).$ Lorenzo may buy a whole number of gallons of gas at each station,

and pays ci per gallon at station gi$.$ Lorenzo starts at g$1$ with $0$ gallons and ends at gn$.$ His tank holds at most

C gallons of gas at once, and he gets m miles per gallon. Station gi is distance di away from g$1,$ and the distance

$|$di $$ di$1|$ is a multiple of m but less than Cm for every i $>1.$ The problem we are interested in is the following:

given g$1,...,$ gn$,$ d$1,...,$ dn$,$ C and m$,$ find how much gas Lorenzo would need to buy at each station to reach gn while

minimizing the amount he pays for gas.

$($a$)$ Define a subproblem and give a recurrence relation that will help you solve this problem, and sketch a proof

that it is correct.

$($b$)$ Describe an algorithm that solves this problem based on your answer to $($a$),$ and state its runtime $($with

sketched proof$)$