You have decided to drive from City A to city B and you want to figure out which hotels you should stay at along the way. Assume that there is only one highway from City A to City B$,$ that is exactly n miles long and that there is exactly one hotel at each mile along this highway. Each day, you can drive at most k miles and then, if you have not reached B$,$ you must stop at a hotel for the night. Given the price of staying at each hotel for one night, you want to find the minimum possible total amount of money that you can spend spend on hotel during your trip. Give a dynamic programming based algorithm for this problem. Justify the correctness of your algorithm and find the time complexity. Example: Suppose n$=10,$k$=3$ and the costs of the hotels, in order, are $3,1,4,5,2,3,7,8,1($note that there are only $9$ hotels because after you have driven $10$ miles, you have reached City B and do not need a hotel$).$ Then the minimum total cost is $7,$ which can be obtained by staying at the hotels at miles$2,5,6$ and $9.$ Note that you only need to return the minimum cost not the hotel IDs