Hotel Rewards

You are touring Europe for $N$ nights and you sleep in a different city every night. You have already picked the hotel for each city, so you know the price $P_i$ of the room you take on night $i$ for $i = 1, 2, \dots, N$.

You book every room through a website that runs a rewards program. Each night you sleep in a hotel booked through that website you earn one point. Whenever your account holds at least $K$ points you may spend $K$ of them on one free night in any hotel. A free night earns no point.

For example, take $N = 6$ and $K = 2$ with prices $P_1 = 10$, $P_2 = 3$, $P_3 = 12$, $P_4 = 15$, $P_5 = 12$ and $P_6 = 18$. Paying for the first four nights leaves four points in the account, and those cover the last two nights for free, for a total of $P_1 + P_2 + P_3 + P_4 = 40$. If instead you spend two of the three points earned in the first three nights on the fourth night, you can pay for the fifth night and use the last two points on the sixth. That plan costs $P_1 + P_2 + P_3 + P_5 = 37$, which is cheaper.

Write a program that finds the minimum possible total cost of your accommodation. Every hotel you want always has a room free for you, and the order of the cities cannot be changed.

The first line contains two integers $N$ and $K$, the number of nights of the trip and the number of points one free night costs ($1 \le N, K \le 10^5$).

The second line contains $N$ integers $P_1, P_2, \dots, P_N$, where $P_i$ is the price of the room you take on night $i$ ($1 \le P_i \le 10^4$).

Print one integer, the minimum total cost of the accommodation.