Команда из лучших

В школе выбирают команду на турнир. У каждого ученика есть «рейтинг полезности» — неотрицательное целое число. Учитель хочет взять ровно k учеников так, чтобы суммарный рейтинг команды был как можно больше.

Нужно узнать, какой максимальной может быть сумма.

Важно: на олимпиадах сумма может не помещаться в 32-битный тип (используйте 64-битные целые; в Python это не проблема).

Формат ввода

В первой строке записаны два целых числа n и k. Во второй строке записаны n целых чисел a1, a2, ..., an — рейтинги учеников.

Формат вывода

Выведите одно число — максимальную возможную сумму рейтингов выбранных k учеников.

Ограничения

• 1 ≤ n ≤ 50000
• 1 ≤ k ≤ 3000
• 1 ≤ k ≤ n
• 0 ≤ ai ≤ 100000

Пример

Ввод:

5 2
1 100 2 99 3

Вывод:

199

В этом примере выгодно взять учеников с рейтингами 100 и 99.

Ключевое наблюдение: если у тебя уже выбраны k учеников, и среди выбранных есть кто-то с рейтингом x, а среди невыбранных есть рейтинг y > x, то заменой x на y сумма строго увеличится. Значит, в оптимальном наборе не может быть «пропущенного» большего числа — нужно брать самые большие значения.

Почему работает жадность: цель — максимальная сумма без дополнительных ограничений (не важны позиции, совместимость и т.п.). Поэтому любой выбор можно улучшать локальными заменами, пока не останутся k максимальных рейтингов.

План решения:

• Прочитай n, k и массив рейтингов a.
• Отсортируй a по убыванию.
• Возьми первые k элементов и посчитай их сумму.
• Мини-сниппет: a.sort(reverse=True) и ans = sum(a[:k]).
• Выведи ans.

Сложность: сортировка занимает O(n log n), суммирование первых k — O(k). При n до 3000 это легко проходит.

Частая ошибка: сортировать по возрастанию и случайно суммировать первые k (получится минимум). Если сортируешь по возрастанию, тогда бери последние k: sum(a[n-k:]).