#FESTIVAL. Crowded Music 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 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

</p>