#include <bits/stdc++.h>
using namespace std;
void PrintMap(map<int, int> mp) {
  for (auto a : mp) {
    cout << a.first << "->" << a.second << endl;
  }
}
long long int modular(int base, unsigned int exp, unsigned int mod) {
  long long int x = 1;
  long long int power = base % mod;
  for (int i = 0; i < sizeof(int) * 8; i++) {
    int least_sig_bit = 0x00000001 & (exp >> i);
    if (least_sig_bit) x = (x * power) % mod;
    power = (power * power) % mod;
  }
  return x;
}
int subset(vector<int> arr, int l, int r, int sum = 0, int res = 0) {
  if (l > r) {
    if (sum == r - l + 1) {
      cout << "REs" << res << endl;
      res++;
    }
    return res;
  }
  return subset(arr, l + 1, r, sum + arr[l], res);
  return subset(arr, l + 1, r, sum, res);
}
bool isPerfect(unsigned long long int N) {
  if ((sqrt(N) - floor(sqrt(N))) != 0) return false;
  return true;
}
int merge(int arr[], int temp[], int left, int mid, int right) {
  int inv_count = 0;
  int i = left;
  int j = mid;
  int k = left;
  while ((i <= mid - 1) && (j <= right)) {
    if (arr[i] <= arr[j])
      temp[k++] = arr[i++];
    else {
      temp[k++] = arr[j++];
      inv_count = inv_count + (mid - i);
    }
  }
  while (i <= mid - 1) temp[k++] = arr[i++];
  while (j <= right) temp[k++] = arr[j++];
  for (i = left; i <= right; i++) arr[i] = temp[i];
  return inv_count;
}
int _mergeSort(int arr[], int temp[], int left, int right) {
  int mid, inv_count = 0;
  if (right > left) {
    mid = (right + left) / 2;
    inv_count = _mergeSort(arr, temp, left, mid);
    inv_count += _mergeSort(arr, temp, mid + 1, right);
    inv_count += merge(arr, temp, left, mid + 1, right);
  }
  return inv_count;
}
int countSwaps(int arr[], int n) {
  int temp[n];
  return _mergeSort(arr, temp, 0, n - 1);
}
bool arraySortedOrNot(vector<int> arr, int n) {
  if (n == 0 || n == 1) return true;
  for (int i = 1; i < n; i++) {
    if (arr[i - 1] > arr[i]) return false;
  }
  return true;
}
bool isSubsequemce(string s1, string s2, int m, int n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (s1[m - 1] == s2[n - 1]) {
    return isSubsequemce(s1, s2, m - 1, n - 1);
  }
  return isSubsequemce(s1, s2, m, n - 1);
}
int search(int money, vector<int> &arr) {
  for (int i = 0; i < arr.size(); i++) {
    if (arr[i] >= money) {
      return i;
    }
  }
  return arr.size() - 1;
}
int binary(long long int coins, vector<long long int> prices) {
  long long int start = 0;
  long long int end = prices.size() - 1;
  long long int ans_index = -1;
  while (start <= end) {
    int mid = (start + end) / 2;
    if (prices[mid] > coins) {
      end = mid - 1;
    } else {
      ans_index = mid;
      start = mid + 1;
    }
  }
  return (ans_index);
}
vector<int> prefix_sum(vector<int> prices) {
  vector<int> prefix(prices[prices.size() - 1] + 1, prices[prices.size() - 1]);
  int start = 0;
  int last_value = 0;
  for (int i = 0; i < prices.size(); i++) {
    for (int j = start; j < prices[i]; j++) {
      prefix[j] = last_value;
    }
    prefix[prices[i]] = last_value + 1;
    start = prices[i] + 1;
    last_value += 1;
  }
  return prefix;
}
bool compareSize(string s1, string s2) { return (s1.size() < s2.size()); }
bool isSubstr(string s1, string s2) {
  int M = s1.length();
  int N = s2.length();
  for (int i = 0; i <= N - M; i++) {
    int j;
    for (j = 0; j < M; j++)
      if (s2[i + j] != s1[j]) break;
    if (j == M) return true;
  }
  return false;
}
int main() {
  long long int testcase;
  cin >> testcase;
  while (testcase--) {
    long long int n, k;
    cin >> n >> k;
    vector<long long int> arr(n);
    for (int i = 0; i < n; i++) {
      cin >> arr[i];
    }
    sort(arr.begin(), arr.end(), greater<long long int>());
    if (k == 0 || n == 1) {
      cout << (arr[0] - arr[n - 1]) << endl;
      continue;
    }
    long long int max_diff = arr[0];
    for (long long int i = 1; i < min(k + 1, n); i++) {
      max_diff += arr[i];
    }
    cout << max_diff << endl;
  }
}

### Prompt

Please create a solution in cpp 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;
void PrintMap(map<int, int> mp) {
  for (auto a : mp) {
    cout << a.first << "->" << a.second << endl;
  }
}
long long int modular(int base, unsigned int exp, unsigned int mod) {
  long long int x = 1;
  long long int power = base % mod;
  for (int i = 0; i < sizeof(int) * 8; i++) {
    int least_sig_bit = 0x00000001 & (exp >> i);
    if (least_sig_bit) x = (x * power) % mod;
    power = (power * power) % mod;
  }
  return x;
}
int subset(vector<int> arr, int l, int r, int sum = 0, int res = 0) {
  if (l > r) {
    if (sum == r - l + 1) {
      cout << "REs" << res << endl;
      res++;
    }
    return res;
  }
  return subset(arr, l + 1, r, sum + arr[l], res);
  return subset(arr, l + 1, r, sum, res);
}
bool isPerfect(unsigned long long int N) {
  if ((sqrt(N) - floor(sqrt(N))) != 0) return false;
  return true;
}
int merge(int arr[], int temp[], int left, int mid, int right) {
  int inv_count = 0;
  int i = left;
  int j = mid;
  int k = left;
  while ((i <= mid - 1) && (j <= right)) {
    if (arr[i] <= arr[j])
      temp[k++] = arr[i++];
    else {
      temp[k++] = arr[j++];
      inv_count = inv_count + (mid - i);
    }
  }
  while (i <= mid - 1) temp[k++] = arr[i++];
  while (j <= right) temp[k++] = arr[j++];
  for (i = left; i <= right; i++) arr[i] = temp[i];
  return inv_count;
}
int _mergeSort(int arr[], int temp[], int left, int right) {
  int mid, inv_count = 0;
  if (right > left) {
    mid = (right + left) / 2;
    inv_count = _mergeSort(arr, temp, left, mid);
    inv_count += _mergeSort(arr, temp, mid + 1, right);
    inv_count += merge(arr, temp, left, mid + 1, right);
  }
  return inv_count;
}
int countSwaps(int arr[], int n) {
  int temp[n];
  return _mergeSort(arr, temp, 0, n - 1);
}
bool arraySortedOrNot(vector<int> arr, int n) {
  if (n == 0 || n == 1) return true;
  for (int i = 1; i < n; i++) {
    if (arr[i - 1] > arr[i]) return false;
  }
  return true;
}
bool isSubsequemce(string s1, string s2, int m, int n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (s1[m - 1] == s2[n - 1]) {
    return isSubsequemce(s1, s2, m - 1, n - 1);
  }
  return isSubsequemce(s1, s2, m, n - 1);
}
int search(int money, vector<int> &arr) {
  for (int i = 0; i < arr.size(); i++) {
    if (arr[i] >= money) {
      return i;
    }
  }
  return arr.size() - 1;
}
int binary(long long int coins, vector<long long int> prices) {
  long long int start = 0;
  long long int end = prices.size() - 1;
  long long int ans_index = -1;
  while (start <= end) {
    int mid = (start + end) / 2;
    if (prices[mid] > coins) {
      end = mid - 1;
    } else {
      ans_index = mid;
      start = mid + 1;
    }
  }
  return (ans_index);
}
vector<int> prefix_sum(vector<int> prices) {
  vector<int> prefix(prices[prices.size() - 1] + 1, prices[prices.size() - 1]);
  int start = 0;
  int last_value = 0;
  for (int i = 0; i < prices.size(); i++) {
    for (int j = start; j < prices[i]; j++) {
      prefix[j] = last_value;
    }
    prefix[prices[i]] = last_value + 1;
    start = prices[i] + 1;
    last_value += 1;
  }
  return prefix;
}
bool compareSize(string s1, string s2) { return (s1.size() < s2.size()); }
bool isSubstr(string s1, string s2) {
  int M = s1.length();
  int N = s2.length();
  for (int i = 0; i <= N - M; i++) {
    int j;
    for (j = 0; j < M; j++)
      if (s2[i + j] != s1[j]) break;
    if (j == M) return true;
  }
  return false;
}
int main() {
  long long int testcase;
  cin >> testcase;
  while (testcase--) {
    long long int n, k;
    cin >> n >> k;
    vector<long long int> arr(n);
    for (int i = 0; i < n; i++) {
      cin >> arr[i];
    }
    sort(arr.begin(), arr.end(), greater<long long int>());
    if (k == 0 || n == 1) {
      cout << (arr[0] - arr[n - 1]) << endl;
      continue;
    }
    long long int max_diff = arr[0];
    for (long long int i = 1; i < min(k + 1, n); i++) {
      max_diff += arr[i];
    }
    cout << max_diff << endl;
  }
}

```