Codah ClubExersează. Trimite. Progresează.
Autentificare
Română
#000050

z-paradajz

Mr. Little Z wants to live a healthy life, so he decided to eat exactly one tomato every day.


The price of tomatoes changes every day, so Mr. Little Z went to a fortune teller to get predictions for the prices of tomatoes for the next n days. Mr. Little will buy tomatoes the most optimal way, because he wants to save some money. However, he must make sure that the tomatoes do not go bad. To be more accurate, if you buy a tomato on the i-th day it will be healthy until the (i+d-1)th day. So, the lifespan of a tomato is d. *Important: Mr. Little Z can buy as many tomatoes as he wants in one day!


For the given tomatoes' prices in the next n days and the lifespan of tomatoes d, calculate the minimum amount of money that Mr. Little Z has to spend in order to eat one tomato for each of the next n days.


InputThe first line of the standard input contains two numbers, n and d. 1 <= n, d <= 200000, where d <= n. Each of the next n lines contains prices for tomatoes ci (i = 1..n), where the maximum price for each tomato is 1000.

OutputTo the standard output write one number corresponding to the minimum amount of money Mr. Little Z has to spend in order to eat one tomato every day.

Input:
8 3
1
2
3
2
4
1
3
2
Output:
10
Explanation: Mr. Little Z will buy 3 tomatoes on the 1st day, then he'll buy 2 tomatoes on the 4th day, and finally he will buy 3 tomatoes on the 6th day.

Comment: Mr. Little Z can eat a tomato on the same day he bought it.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.