Hotel Rewards

You are planning to spend your holidays touring Europe, staying each night in a different city for N consecutive nights. You have already chosen the hotel you want to stay in for each city, so you know the price P_i of the room you’ll be staying at during the i-th night of your holidays, for i = 1, . . . ,N.

You will book your accommodation through a website that has a very convenient rewards program, which works as follows. After staying for a night in a hotel you booked through this website you are awarded one point, and at any time you can exchange K of these points in your account for a free night in any hotel (which will however not give you another point).

For example, consider the case with N = 6 and K = 2 where the prices for the rooms are P₁ = 10, P₂ = 3, P₃ = 12, P₄ = 15, P₅ = 12 and P₆ = 18. After paying for the first four nights you would have four points in your account, which you could exchange to stay for free the remaining two nights, paying a total of P₁ + P₂ + P₃ + P₄ = 40 for your accommodation. However, if after the first three nights you use two of the three points you earned to stay the fourth night for free, then you can pay for the fifth night and use the final two points to get the sixth one for free. In this case, the total cost of your accommodation is P₁ + P₂ + P₃ + P₅ = 37, so this option is actually more convenient.

You want to make a program to find out what the minimum possible cost for your holidays’ accommodation is. You can safely assume that all hotels you want to stay always will have a room available for you, and that the order of the cities you are going to visit cannot be altered.