As some of his students are not eating their fruits, Rabbit had to bring them home. Thus, he now has N bananas.
Rabbit likes banana smoothies. Thus, he has decided to make them into banana smoothies. It takes K bananas to make a banana smoothie.
Bananas have different quality, which affect the banana smoothie. Each banana has quality Qi, and as Rabbit has very sensitive taste buds, the quality of a smoothie is given by the minimum quality of all bananas used to make the smoothie.
Rabbit wants to make some smoothies such that the sum of their quality is maximised. Help him find the maximum sum of the quality of the smoothies!
The first line of input contains two integers, N and K.
The next line of input contains N integers, representing the array Q.
The first and only line of output should contain a single integer denoting the maximum sum of the quality of the smoothies.
For all subtasks, 1 ≤ K ≤ N ≤ 100000 and -109 ≤ Qi ≤ 109.
Subtask 1 (10%): K = 1
Subtask 2 (30%): 0 ≤ Qi
Subtask 3 (60%): There are no more constraints.
9 2 3 4 2 3 -1 6
We can make a smoothie using bananas 1, 4 and 8 (1-indexed) with quality 4 and another smoothie using bananas 2, 3 and 5 with quality 2. This adds up to 6, which is the maximum possible.