Array

3.8

12 votes
Medium
Problem

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.

Input

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.

Output

For each test case, print the minimum possible value of the largest element of the array after kth step.

Constraints

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

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?