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