You are given an array of size n containing initial values a1, a2, ........, an. You've to perform k step modification to the given array. In each step you can pick any element of array and add its initial value to it.
What is the minimum possible value of the largest element of the modified array after k steps.
First line of input contains an integer T - the number of test cases. The description of T test cases follows.
First line of each test case contains two space separated integers n and k - the size of array and the number of steps respectively.
Second line contains n space separated integers a1, a2, ........, an - initial values of the array.
For each test case, print the minimum possible value of the largest element of the array after kth step.
1 ≤ T ≤ 10
1 ≤ n ≤ 100,000
1 ≤ k ≤ 1,000,000
1 ≤ ai ≤ 1,000,000,000
Subtasks
Subtask #1: (25 points) 1 ≤ n, k ≤ 1,000
Subtask #2: (75 points) Original Constraints
One possible sequence when answer is 8 :
Initial values of array : 2 5 3 6 4
After Step 1 array : 4 5 3 6 4
After Step 2 array : 6 5 3 6 4
After Step 3 array : 6 5 6 6 4
After Step 4 array : 8 5 6 6 4