Festive Stew

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

nicoella is cooking up a stew for the annual Globgalab Christmas Festival!

In Globgalab City, ingredients are all given a flavour value. She has access to an assortment of N tasty ingredients where each ingredient has a flavour value of a_i. nicoella has determined that to achieve the right texture of stew she must use exactly K ingredients.

Additionally, the tastiest stew will use ingredients with the smallest difference in flavour values, that is, the largest difference between two ingredients must be minimized to achieve the tastiest stew. nicoella is having a tough time deciding which ingredients to choose so she has enlisted you with the task of choosing the best ingredients and finding the total flavour value of the ingredients. In the scenario where multiple combinations of ingredients will achieve the smallest difference in flavour values, output the answer in which the sum of the flavour values is maximized.

Can you help her make the tastiest stew with K ingredients?

Input Specification

The first line contains two space-separated integers N, K (1 \le K \le N \le 2 \cdot 10^5)

The second line contains N integers, the flavour value of the ingredients, a_1, a_2, ... , a_N (1 \le a_i \le 1000)

Output Specification

Output a single integer, the sum of the flavour values whose ingredients make the tastiest stew.

Subtasks

Subtask 1 (20%)

N \le 15

Subtask 2 (80%)

No further constraints.

Sample Input

5 3
1 4 2 3 6

Sample Output

9

Comments

There are no comments at the moment.