FESTIVAL  Crowded Music Festival
You are the organizer of a music festival, which lasts for N days. Every day a new band arrives, and plays during K days, as long as the festival is still running. Hence in total N bands are playing at the festival, but not necessarily all on the same day. For the band arriving on day i, you know that X_{i} people are going to attend each of their concerts. Every day you have up to K concerts, and you need to scale the facilities to accommodate for the maximum attendance to the concerts on that day. Scaling the facility on a specific day to accommodate a public of size y, costs you y Euros. Your goal is to compute the total cost over the N days.
Input
The first line contains two integers N and K separated by a space. It is followed by N lines, each containing a single integer X_{i}.
Constraints
1 ≤ N, K ≤ 1 000 000
1 ≤ X_{1}, ..., X_{N} ≤ 1 000 000
Output
Output a single line containing the total cost.
Example
On day 1 you need to accommodate for the unique concert of the day, that is for 6 people. On day 2 you need to accommodate for two concerts, the first one for 6 people and the second one for 2 people, hence for the whole day you need to accommodate for 6 people. On day 3 you need to accommodate for 4 people only. This gives a total cost of 6 + 6 + 4 Euros.
Input: 3 2
6
2
4 Output: 16
hide comments
vl4deee11:
20240501 05:35:43
A little explanation of the example after AC


slothsphereoj:
20240320 05:06:40
Here's the troll part:


flower:
20231126 01:18:05
Good problem to practice a standard technique, with tests that cover edge cases. The description and explanation could have been formulated more clearly. 

smso:
20221108 15:54:05
Poor problem statement and testcase explanation. 

Christoph Dürr:
20211122 10:47:35
Thank you nadstratosfer for your nice words. Indeed, we wanted to make sure that Python solutions are accepted, because we hate when limit limits are too harsh, made sure that the naive solution in C++ will be rejected, give a bit of suspense during the verification with multiple test files. 

nadstratosfer:
20211118 22:50:02
Good use of multiple testfiles here, many methods to try and Py2 passes with a good one.

Added by:  xtof 
Date:  20211118 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  problem invented with my daugther Anita D. Dürr 