B. Cursed Coins
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Alice the adventurer was doing a dungeon run when she encountered a room with $$$n$$$ locked chests, each chest filled with gold coins. Unfortunately, Bob, the evil wizard, cursed some of the chests, and now they contain cursed gold, which takes away from Alice's total coin count instead of increasing it. Alice has $$$k$$$ keys, which she may use to unlock up to $$$k$$$ chests.

You are given an array $$$a$$$, where $$$a_i$$$ represents the number of coins Alice will gain from opening the $$$i$$$-th chest. Note that if the $$$i$$$-th chest is a cursed chest, $$$a_i$$$ is negative.

What is the maximum amount of coins that Alice can end up with, assuming she uses her keys optimally? Alice does not need to use up all her keys, and her account balance starts at $$$0$$$ coins.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of chests and the number of keys, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — the number of coins Alice will gain from opening the $$$i$$$-th chest.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer — the maximum number of coins Alice can loot.

Example
Input
3
2 1
5 10
2 1
5 -10
3 3
1 -2 3
Output
10
5
4
Note

In the first test case, Alice can only choose one chest to open; thus, $$$10$$$ is the maximum number of gold coins that she can loot. In this case, Bob has not cursed any of the chests.

In the second test case, since Bob has cursed the 2nd chest, Alice can optimally open the 1st chest instead, yielding $$$5$$$ coins.