You are given an array $$$a_1, a_2, \dots, a_n$$$, where all elements are different.
You have to perform exactly $$$k$$$ operations with it. During each operation, you do exactly one of the following two actions (you choose which to do yourself):
You have to calculate the maximum possible sum of elements in the resulting array.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each test case consists of two lines:
Additional constraint on the input: the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.
For each test case, print one integer — the maximum possible sum of elements in the resulting array.
65 12 5 1 10 65 22 5 1 10 63 11 2 36 115 22 12 10 13 116 215 22 12 10 13 115 1999999996 999999999 999999997 999999998 999999995
21 11 3 62 46 3999999986
In the first testcase, applying the first operation produces the following outcome:
$$$21$$$ is the best answer.
In the second testcase, it's optimal to first erase two minimums, then a maximum.
Name |
---|