Banana Smoothie

Problem Statement

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!

Input

The first line of input contains two integers, N and K.

The next line of input contains N integers, representing the array Q.

Output

The first and only line of output should contain a single integer denoting the maximum sum of the quality of the smoothies.

Limits

For all subtasks, 1 ≤ KN ≤ 100000 and -109Qi ≤ 109.

Subtask 1 (10%): K = 1

Subtask 2 (30%): 0 ≤ Qi

Subtask 3 (60%): There are no more constraints.

Sample Input

8 3
9 2 3 4 2 3 -1 6

Sample Output

6

Explanation

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.

Submitting to 'Banana Smoothie'


You're not logged in! Click here to login


Submitting to 'Banana Smoothie'


You're not logged in! Click here to login


Submitting .cpp to 'Banana Smoothie'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 87
Your best score: 0
Source: Dunjudge Archive (shenxy13)

Subtask Score
1 10
2 30
3 60
4 0