Ciel and Eggs

All submissions for this problem are available.

Chef Ciel has N strange eggs. The i-th egg is broken by tapping exactly A_i times. Ciel needs to break K eggs as soon as possible for cooking a rice omelet. However she has been put in an uncomfortable situation. Someone shuffled the eggs! Ciel knows the values A_i, however she doesn't know which egg is which. She'd like to minimize the worst-case number of taps. What is the minimal number?

Input

The first line contains an integer T, the number of test cases. Then T test cases follow. The first line for each test case has 2 integers N and K. Then next line has N integers A₁, A₂, ..., A_N.

Output

For each test case, print the minimal number of taps for the worst-case.

Constraints

1 ≤ T ≤ 10
1 ≤ K ≤ N ≤ 500
1 ≤ A_i ≤ 1000000 (10⁶)

Sample Input

3
2 1
5 8
2 1
5 58
3 2
1 2 3

Sample Output

8
10
5

Output details

In the first case, if a egg isn't broken after 5 taps, she should continue to tap the same egg.

In the second case, if a egg isn't broken after 5 taps, she should tap another egg 5 times.

---

Date:	2011-08-23
Time limit:	8s
Source limit:	50000B
Languages:	All