SPOJ.com - Problem FESTIVAL

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₁, ..., 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

Submit solution!

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

hide comments



2024-05-01 05:35:43 A little explanation of the example after AC 1. On the first day - 6 people 2. On the second day there are two concerts (the first one goes 2 times, the second one goes 1 time) - 6 people for the first and 2 people for the second, since there is only one hall, we need to make it so big that all people fit, for a total of 6 people 3. On the third day there are two concerts (the second one goes 2 times, the third one goes 1 time) - 2 people for the second and 4 people for the third, since there is only one hall, we need to make it so big that all people fit, for a total of 4 people total = 6 + 6 + 4 Just assume that all the concerts are in one hall and you need to find a size for day 'i' so that all the concerts taking place on that day fit in this hall Last edit: 2024-05-01 05:36:18
2024-03-20 05:06:40 Here's the troll part: It is possible that K > N, N = total number of days of performance, K = number of days the band performs music.
2023-11-26 01:18:05 flower Good problem to practice a standard technique, with tests that cover edge cases. The description and explanation could have been formulated more clearly.
2022-11-08 15:54:05 Poor problem statement and testcase explanation.
2021-11-22 10:47:35 Christoph Dürr 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.
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 =)