FESTIVAL - Crowded Music Festival

no tags 

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 Xi 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.

Music Festival

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 Xi.

Constraints

1 ≤ N, K ≤ 1 000 000
1 ≤ X1, ..., XN ≤ 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
Christoph Dürr: 2021-11-22 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: 2021-11-18 22:50:02

Good use of multiple testfiles here, many methods to try and Py2 passes with a good one.

Greetings to Anita, I confirm that daughters, problems and coders go well together =)


Added by:xtof
Date:2021-11-18
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