Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Barrels

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have $$$n$$$ barrels lined up in a row, numbered from left to right from one. Initially, the $$$i$$$-th barrel contains $$$a_i$$$ liters of water.

You can pour water from one barrel to another. In one act of pouring, you can choose two different barrels $$$x$$$ and $$$y$$$ (the $$$x$$$-th barrel shouldn't be empty) and pour any possible amount of water from barrel $$$x$$$ to barrel $$$y$$$ (possibly, all water). You may assume that barrels have infinite capacity, so you can pour any amount of water in each of them.

Calculate the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $$$k$$$ times.

Some examples:

- if you have four barrels, each containing $$$5$$$ liters of water, and $$$k = 1$$$, you may pour $$$5$$$ liters from the second barrel into the fourth, so the amounts of water in the barrels are $$$[5, 0, 5, 10]$$$, and the difference between the maximum and the minimum is $$$10$$$;
- if all barrels are empty, you can't make any operation, so the difference between the maximum and the minimum amount is still $$$0$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$) — the number of barrels and the number of pourings you can make.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), where $$$a_i$$$ is the initial amount of water the $$$i$$$-th barrel has.

It's guaranteed that the total sum of $$$n$$$ over test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $$$k$$$ times.

Example

Input

2 4 1 5 5 5 5 3 2 0 0 0

Output

10 0

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/23/2021 02:17:07 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|