Дан массив \(a_1, a_2, \dots, a_n\), в котором все элементы различны.
Вы должны выполнить ровно \(k\) операций с ним. Во время каждой операции вы выполняете ровно одно из следующих двух действий (вы самостоятельно выбираете, какое именно):
- найти два минимальных элемента в массиве и удалить их;
- найти максимальный элемент в массиве и удалить его.
Вы должны вычислить максимальную возможную сумму элементов в полученном массиве.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную возможную сумму элементов в полученном массиве.
Примечание
В первом наборе входных данных применение первой операции приводит к следующему результату:
- два минимума равны \(1\) и \(2\); их удаление оставляет массив \([5, 10, 6]\) с суммой \(21\);
- максимум равен \(10\); его удаление оставляет массив \([2, 5, 1, 6]\) с суммой \(14\).
\(21\) — лучший ответ.
Во втором наборе входных данных оптимально сначала удалить два минимума, а затем максимум.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 1
2 5 1 10 6
5 2
2 5 1 10 6
3 1
1 2 3
6 1
15 22 12 10 13 11
6 2
15 22 12 10 13 11
5 1
999999996 999999999 999999997 999999998 999999995
|
21
11
3
62
46
3999999986
|