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 \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

Difficulty: interview

Starter code:

Solutions:
def solve():
    n, k = map(int,input().split())
    lst = list(map(int,input().split()))
    lst.sort()
    ans = 0
    for i in range(n - k - 1, n):
        ans += lst[i]
    print(ans)
for i in range(int(input())):
    solve()

t=int(input())
for i in range(t):
    n,k=[int(i) for i in input().split()]
    a=[int(i) for i in input().split()]
    a.sort(reverse=True)
    print(sum(a[:k+1]))

# map(int, input().split())
rw = int(input())
for wewq in range(rw):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.sort()
    a.reverse()
    f = 0
    for i in range(k + 1):
        f += a[i]
    print(f)


t=int(input())
for you in range(t):
    l=input().split()
    n=int(l[0])
    k=int(l[1])
    l=input().split()
    li=[int(i) for i in l]
    if(k==0):
        print(max(li)-min(li))
        continue
    z=0
    li.sort()
    li.reverse()
    for i in range(k+1):
        z+=li[i]
    print(z)


for _ in range (int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    for i in range (1,k+1):
        a[0]+=a[i]
        a[i]=0
    print(a[0]-a[1])

for __ in range(int(input())):
    n, k = list(map(int, input().split()))
    ar = list(map(int, input().split()))
    ar.sort(reverse=True)
    ans = 0
    for i in range(min(n, k + 1)):
        ans += ar[i]
    print(ans)

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod=10**9+7


for t in range(int(data())):
    n,k=mdata()
    a=sorted(mdata(),reverse=True)
    s=sum(a[:k+1])
    out(s)


import sys
input = sys.stdin.readline

t = int(input())
for i in range(t):
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort()
    a.reverse()
    cum = [a[0]]
    for i in range(n-1):
        cum.append(cum[i]+a[i+1])
    cum.append(cum[-1])
    print(cum[k])

t = int(input())
for _ in range(t):
    #n = int(input())
    n, k=map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s=0
    for i in range(k+1):
        s+=a[n-1-i]
    print(s)

def main():
    N, K = list(map(int, input().split()))
    *A, = list(map(int, input().split()))
    
    A.sort()
    print(A[-1] + sum(A[-K-1:-1]))

def __starting_point():
    for __ in [0]*int(input()):
        main()

__starting_point()

import sys
import random
# import numpy as np
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)
# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")

MOD = 10 ** 9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def judge(at, ax, ay, bt, bx, by):
    if abs(at - bt) >= abs(ax - bx) + abs(ay - by):
        return True
    else:
        return False


def solve():
    n, k = getList()
    li = getList()

    if k >= n:
        print(sum(li))
        return

    li.sort(reverse=True)
    print(sum(li[:k+1]))

    return

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
def __starting_point():
    main()
    # solve()

__starting_point()

from sys import stdin
t = int(stdin.readline())
for _ in range(t):
    n, k = tuple(int(x) for x in stdin.readline().split())
    lst = sorted(int(x) for x in stdin.readline().split())
    print(sum(lst[-k-1:]))


t = int(input())
for _ in range(t):
    n,k = [int(x) for x in input().split()]
    l = [int(x) for x in input().split()]
    l.sort()
    l.reverse()
    print(sum(l[:min(k+1,n)]))

for _ in range(int(input())):
	n, k = list(map(int, input().split()))
	A = list(map(int, input().split()))

	A.sort(reverse=True)
	if k == 0:
		print(max(A) - min(A))
	else:
		print(A[0] + sum(A[1:k+1]))


n = int(input())

for _ in range(n):
    n, k = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    arr.sort(reverse=True)

    print(sum(arr[:k+1]))


"""T=int(input())
for _ in range(0,T):
    n=int(input())
    a,b=map(int,input().split())
    s=input()
    s=[int(x) for x in input().split()]
    for i in range(0,len(s)):
        a,b=map(int,input().split())"""


T=int(input())
for _ in range(0,T):
    n,k=list(map(int,input().split()))
    s=[int(x) for x in input().split()]
    s.sort()
    s=s[::-1]
    for i in range(1,min(k+1,len(s))):
        s[0]+=s[i]

    print(s[0])


t=int(input())
while t:
	t-=1
	n,k=list(map(int,input().split()))
	a=[int(i) for i in input().split()]
	a.sort()
	ans=0
	a.reverse()
	for i in range(k+1):
		ans+=a[i]
		
	print(ans)