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