#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
long long mul(long long a, long long b, long long p = 1000000007) {
  return ((a % p) * (b % p)) % p;
}
long long add(long long a, long long b, long long p = 1000000007) {
  return (a % p + b % p) % p;
}
void input(long long a[], long long sz) {
  for (long long i = 0; i < sz; i++) cin >> a[i];
}
void print(long long a[], long long sz) {
  for (long long i = 0; i < sz; i++) {
    if (i == sz - 1)
      cout << a[i] << "\n";
    else
      cout << a[i] << " ";
  }
}
long long maxr(long long a[], long long sz) {
  long long ma;
  for (long long i = 0; i < sz; i++) {
    if (i == 0)
      ma = a[i];
    else if (a[i] > ma)
      ma = a[i];
  }
  return ma;
}
long long minr(long long a[], long long sz) {
  long long mi;
  for (long long i = 0; i < sz; i++) {
    if (i == 0)
      mi = a[i];
    else if (a[i] < mi)
      mi = a[i];
  }
  return mi;
}
long long isprm(long long n) {
  if (n <= 1) return 0;
  if (n <= 3) return 1;
  if (n % 2 == 0 || n % 3 == 0) return 0;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return 0;
  return 1;
}
long long power(long long x, long long y, long long p = 1000000007) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInverse(long long n, long long p = 1000000007) {
  return power(n, p - 2, p);
}
struct comp {
  bool operator()(const pair<long long, long long> &a,
                  const pair<long long, long long> &b) const {
    if (a.first == b.first) {
      return (a.second > b.second);
    }
    return (a.first < b.first);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    long long a[n + 5];
    input(a, n);
    sort(a, a + n, greater<long long>());
    for (long long i = 1; i < k + 1; i++) {
      a[0] += a[i];
      a[i] = 0;
    }
    long long ans = a[0];
    cout << ans << "\n";
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

You 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 ≤ t ≤ 1000) — the number of test cases.

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

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 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 ⋅ 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
long long mul(long long a, long long b, long long p = 1000000007) {
  return ((a % p) * (b % p)) % p;
}
long long add(long long a, long long b, long long p = 1000000007) {
  return (a % p + b % p) % p;
}
void input(long long a[], long long sz) {
  for (long long i = 0; i < sz; i++) cin >> a[i];
}
void print(long long a[], long long sz) {
  for (long long i = 0; i < sz; i++) {
    if (i == sz - 1)
      cout << a[i] << "\n";
    else
      cout << a[i] << " ";
  }
}
long long maxr(long long a[], long long sz) {
  long long ma;
  for (long long i = 0; i < sz; i++) {
    if (i == 0)
      ma = a[i];
    else if (a[i] > ma)
      ma = a[i];
  }
  return ma;
}
long long minr(long long a[], long long sz) {
  long long mi;
  for (long long i = 0; i < sz; i++) {
    if (i == 0)
      mi = a[i];
    else if (a[i] < mi)
      mi = a[i];
  }
  return mi;
}
long long isprm(long long n) {
  if (n <= 1) return 0;
  if (n <= 3) return 1;
  if (n % 2 == 0 || n % 3 == 0) return 0;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return 0;
  return 1;
}
long long power(long long x, long long y, long long p = 1000000007) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInverse(long long n, long long p = 1000000007) {
  return power(n, p - 2, p);
}
struct comp {
  bool operator()(const pair<long long, long long> &a,
                  const pair<long long, long long> &b) const {
    if (a.first == b.first) {
      return (a.second > b.second);
    }
    return (a.first < b.first);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    long long a[n + 5];
    input(a, n);
    sort(a, a + n, greater<long long>());
    for (long long i = 1; i < k + 1; i++) {
      a[0] += a[i];
      a[i] = 0;
    }
    long long ans = a[0];
    cout << ans << "\n";
  }
  return 0;
}

```