Trigger the chutes and protect the jackpot You are going to participate in a gameshow. One of the challenges works as follows:


The first room contains a large number of identical balls.
The second room contains a series of chutes, each of which has a sensor which counts how many balls have been placed in it. A ball which is placed in a chute cannot then be recovered.
Each chute will trigger after a certain number of balls (its trigger count) have been placed into it. When it triggers it flashes lights, makes a noise, and leaves you in no doubt that it has triggered.
You must trigger N chutes to continue to the next challenge.
You know the trigger counts, but not the correspondence between count and chute.
You have one opportunity to take balls from the first room into the second. Once you put a ball into a chute, you cannot go back for more balls.
Each ball which you take deducts money from the jackpot.


Obviously you want to ensure that you will pass the challenge, but you want to minimise the jackpot money loss. Write a program, function, verb, etc. to tell you how many balls you need.

Example

Suppose the trigger counts are 2, 4, and 10, and you need to trigger 2 chutes to pass. There is a strategy to pass with 10 balls: place up to 4 balls in the first chute, up to 4 balls in the second chute, and up to 4 balls in the third chute. Since one of the three chutes will trigger after only 2 balls, you only use a total of 10. There is no strategy which is guaranteed to work with fewer than 10, so that is the correct output.

Input

The input consists of an array of integer trigger counts and a integer giving the number of chutes to trigger. You may take the two inputs in either order, and if needed you may take a third input with the length of the array.

You may assume that all of the inputs are greater than zero, and that the number of chutes which must be triggered does not exceed the number of chutes.

You may also assume that the counts are sorted (ascending or descending), as long as you state that clearly in your answer.

Output

The output should be a single integer, giving the number of balls required by the optimum strategy.

Test cases

Format: N counts solution

1 [2 4 10] 6
2 [2 4 10] 10
3 [2 4 10] 16
1 [3 5 5 5 5 5 5 5 5 5] 5
2 [1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 8 11] 8
2 [1 2 6 6 6 6 6 6 6 10] 16
2 [1 2 3 3 4 4 6 6 6 11] 17
3 [1 2 3 4 5 5 6] 16
3 [2 4 7 7 7 7 7 7 7] 21
5 [1 2 2 3 3 3 3 3 5 9 9 11] 27
2 [5 15 15] 25
1 [4 5 15] 10
3 [1 4 4 4] 10
2 [1 3 4] 6
2 [1 3 3 8] 8
Python, 222 198 bytes

def S(G,P,T=0):
 T=T or[0]*len(P);r=[0]*(sum(t&gt;=p for t,p in zip(T,P))&gt;=G)
 for i,t in enumerate(T):
    if t&lt;max(P):a=next(p for p in P if p&gt;t)-t;T[i]+=a;r+=[a+S(G,P,sorted(T))];T[i]-=a
 return min(r)


Usage is S(2, (2, 4, 10)).

In order to test this program at any decent speed, add memoization by putting this after the function definition:

old_s = S
mem = {}
def S(G, P, T=0):
    k = (G, tuple(P), T and tuple(T) or 0)
    if k in mem: return mem[k]
    r = old_s(G, P, T)
    mem[k] = r
    return r




We do dynamic programming on an array T that contains the number of balls we've thrown into each chute, initially all zeroes. Without providing a rigorous proof, I claim that we can keep T sorted at all times, that is, assume we always throw the most balls into the last chute, which in turn we will assume was the largest chute.

If then T, when matched element for element with P (which is our problem input), has at least G (which is our goal) elements bigger, we've found a solution, and we return 0, because we need to throw 0 more balls to find a solution. This means that if G is 1 our least thrown into chute must contain an equal or more amount of balls than the smallest chute requirement, and so on for bigger G.

Otherwise, for each position we throw in enough balls to upgrade to the next chute requirement (anything in between would never be observable) and recurse. We then return the minimum of these recursive calls.