#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
template <typename T>
void read(T &x) {
  cin >> x;
}
template <typename T, typename T0>
void read(T &x, T0 &y) {
  cin >> x >> y;
}
template <typename T, typename T0, typename T1>
void read(T &x, T0 &y, T1 &z) {
  cin >> x >> y >> z;
}
template <typename T, typename T0, typename T1, typename T2>
void read(T &x, T0 &y, T1 &z, T2 &w) {
  cin >> x >> y >> z >> w;
}
template <typename T, typename T0>
void read(pair<T, T0> &p) {
  cin >> p.first >> p.second;
}
template <typename T>
void read(vector<T> &oneD, long long int n) {
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int x;
    read(x);
    oneD.push_back(x);
  }
}
template <typename T>
void read(T oneD[], long long int n) {
  for (long long int i = 0; i < n; i++) {
    read(oneD[i]);
  }
}
template <typename T>
void write(T &x) {
  cout << x << " ";
}
template <typename T, typename T0>
void write(T &x, T0 &y) {
  cout << x << " " << y << "\n";
}
template <typename T, typename T0, typename T1>
void write(T &x, T0 &y, T1 &z) {
  cout << x << " " << y << " " << z << "\n";
}
template <typename T, typename T0, typename T1, typename T2>
void write(T &x, T0 &y, T1 &z, T2 &w) {
  cout << x << " " << y << " " << z << " " << w << "\n";
}
template <typename T, typename T0>
void write(pair<T, T0> &p) {
  write(p.first);
  write(p.second);
  cout << endl;
}
template <typename T>
void write(vector<T> &oneD, long long int n) {
  for (long long int i = 0; i < n; i++) {
    cout << oneD[i] << " ";
  }
  cout << endl;
}
template <typename T>
void write(T oneD[], int n) {
  for (long long int i = 0; i < n; i++) {
    write(oneD[i]);
  }
  cout << endl;
}
template <typename T, typename T0>
void write(map<T, T0> &mpp) {
  for (auto it : mpp) {
    write(it.first);
    cout << ": ";
    write(it.second);
    cout << "\n";
  }
  cout << endl;
}
vector<long long int> seive;
void Seive() {
  const long long int maxn = 1e6 + 5;
  seive.resize(maxn);
  for (long long int(i) = 0; (i) < (maxn); ++(i)) seive[i] = i;
  for (long long int(i) = 2; (i) <= (maxn); (i) += (2)) seive[i] = 2;
  seive[1] = -1;
  seive[0] = -1;
  for (long long int i = 3; i <= maxn; i += 2)
    if (i == seive[i])
      for (long long int j = i * i; j < maxn; j += i)
        if (seive[j] == j) seive[j] = i;
}
long long int extended_GCD(long long int a, long long int b, long long int &x,
                           long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod = 1000000007) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int find_x_CRT(long long int num[], long long int rem[],
                         long long int n) {
  long long int pro = 1;
  for (long long int(i) = 0; (i) < (n); ++(i)) pro *= num[i];
  long long int res = 0;
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int pp = pro / num[i];
    res += (rem[i] * modinv(pp, num[i]) * pp);
  }
  res %= pro;
  return res;
}
long long int power(long long int a, long long int b,
                    long long int m = 1000000007) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int powe(long long int a, long long int b,
                   long long int m = 1000000007) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
string getString(char x) {
  string s(1, x);
  return s;
}
void precompute_NCR(vector<long long int> &fact) {
  const long long int N = 1e6 + 5;
  fact[0] = 1;
  for (long long int(i) = 1; (i) <= ((N - 1)); (i) += (1)) {
    long long int y = (i % 1000000007 * fact[i - 1] % 1000000007) % 1000000007;
    fact[i] = y;
  }
}
long long int NCR(vector<long long int> &fact, long long int N, long long int R,
                  long long int mod = 1000000007) {
  long long int n = fact[N];
  long long int r = fact[R];
  long long int n_r = fact[N - R];
  long long int y = (r % mod * n_r % mod) % mod;
  long long int z = modinv(y, mod);
  long long int ans = (n % mod * z % mod) % mod;
  return ans;
}
void shuru_karte_hai_bina_kise_bakchodi_ke() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
}
int main() {
  shuru_karte_hai_bina_kise_bakchodi_ke();
  long long int t;
  read(t);
  while (t--) {
    long long int n, k;
    read(n, k);
    long long int a[n];
    read(a, n);
    sort(a, a + n);
    long long int ma = a[n - 1];
    long long int j = n - 2;
    while (j >= 0 and k > 0) {
      ma += a[j];
      j--;
      k--;
    }
    if (n == 1) {
      cout << "0";
    } else {
      cout << ma;
    }
    cout << "\n";
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
template <typename T>
void read(T &x) {
  cin >> x;
}
template <typename T, typename T0>
void read(T &x, T0 &y) {
  cin >> x >> y;
}
template <typename T, typename T0, typename T1>
void read(T &x, T0 &y, T1 &z) {
  cin >> x >> y >> z;
}
template <typename T, typename T0, typename T1, typename T2>
void read(T &x, T0 &y, T1 &z, T2 &w) {
  cin >> x >> y >> z >> w;
}
template <typename T, typename T0>
void read(pair<T, T0> &p) {
  cin >> p.first >> p.second;
}
template <typename T>
void read(vector<T> &oneD, long long int n) {
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int x;
    read(x);
    oneD.push_back(x);
  }
}
template <typename T>
void read(T oneD[], long long int n) {
  for (long long int i = 0; i < n; i++) {
    read(oneD[i]);
  }
}
template <typename T>
void write(T &x) {
  cout << x << " ";
}
template <typename T, typename T0>
void write(T &x, T0 &y) {
  cout << x << " " << y << "\n";
}
template <typename T, typename T0, typename T1>
void write(T &x, T0 &y, T1 &z) {
  cout << x << " " << y << " " << z << "\n";
}
template <typename T, typename T0, typename T1, typename T2>
void write(T &x, T0 &y, T1 &z, T2 &w) {
  cout << x << " " << y << " " << z << " " << w << "\n";
}
template <typename T, typename T0>
void write(pair<T, T0> &p) {
  write(p.first);
  write(p.second);
  cout << endl;
}
template <typename T>
void write(vector<T> &oneD, long long int n) {
  for (long long int i = 0; i < n; i++) {
    cout << oneD[i] << " ";
  }
  cout << endl;
}
template <typename T>
void write(T oneD[], int n) {
  for (long long int i = 0; i < n; i++) {
    write(oneD[i]);
  }
  cout << endl;
}
template <typename T, typename T0>
void write(map<T, T0> &mpp) {
  for (auto it : mpp) {
    write(it.first);
    cout << ": ";
    write(it.second);
    cout << "\n";
  }
  cout << endl;
}
vector<long long int> seive;
void Seive() {
  const long long int maxn = 1e6 + 5;
  seive.resize(maxn);
  for (long long int(i) = 0; (i) < (maxn); ++(i)) seive[i] = i;
  for (long long int(i) = 2; (i) <= (maxn); (i) += (2)) seive[i] = 2;
  seive[1] = -1;
  seive[0] = -1;
  for (long long int i = 3; i <= maxn; i += 2)
    if (i == seive[i])
      for (long long int j = i * i; j < maxn; j += i)
        if (seive[j] == j) seive[j] = i;
}
long long int extended_GCD(long long int a, long long int b, long long int &x,
                           long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod = 1000000007) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int find_x_CRT(long long int num[], long long int rem[],
                         long long int n) {
  long long int pro = 1;
  for (long long int(i) = 0; (i) < (n); ++(i)) pro *= num[i];
  long long int res = 0;
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int pp = pro / num[i];
    res += (rem[i] * modinv(pp, num[i]) * pp);
  }
  res %= pro;
  return res;
}
long long int power(long long int a, long long int b,
                    long long int m = 1000000007) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int powe(long long int a, long long int b,
                   long long int m = 1000000007) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
string getString(char x) {
  string s(1, x);
  return s;
}
void precompute_NCR(vector<long long int> &fact) {
  const long long int N = 1e6 + 5;
  fact[0] = 1;
  for (long long int(i) = 1; (i) <= ((N - 1)); (i) += (1)) {
    long long int y = (i % 1000000007 * fact[i - 1] % 1000000007) % 1000000007;
    fact[i] = y;
  }
}
long long int NCR(vector<long long int> &fact, long long int N, long long int R,
                  long long int mod = 1000000007) {
  long long int n = fact[N];
  long long int r = fact[R];
  long long int n_r = fact[N - R];
  long long int y = (r % mod * n_r % mod) % mod;
  long long int z = modinv(y, mod);
  long long int ans = (n % mod * z % mod) % mod;
  return ans;
}
void shuru_karte_hai_bina_kise_bakchodi_ke() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
}
int main() {
  shuru_karte_hai_bina_kise_bakchodi_ke();
  long long int t;
  read(t);
  while (t--) {
    long long int n, k;
    read(n, k);
    long long int a[n];
    read(a, n);
    sort(a, a + n);
    long long int ma = a[n - 1];
    long long int j = n - 2;
    while (j >= 0 and k > 0) {
      ma += a[j];
      j--;
      k--;
    }
    if (n == 1) {
      cout << "0";
    } else {
      cout << ma;
    }
    cout << "\n";
  }
  return 0;
}

```