Дан массив \(a_1, a_2, \dots, a_n\), в котором все элементы различны.
Вы должны выполнить ровно \(k\) операций с ним. Во время каждой операции вы выполняете ровно одно из следующих двух действий (вы самостоятельно выбираете, какое именно):
Вы должны вычислить максимальную возможную сумму элементов в полученном массиве.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Каждый набор входных данных состоит из двух строк:
Дополнительное ограничение на входные данные: сумма \(n\) не превышает \(2 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — максимальную возможную сумму элементов в полученном массиве.
В первом наборе входных данных применение первой операции приводит к следующему результату:
\(21\) — лучший ответ.
Во втором наборе входных данных оптимально сначала удалить два минимума, а затем максимум.
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач