There are N (1 ≤ N ≤ 100000) servers and each has a fixed serving time T_i irrespective for any single task.

There are M (1 ≤ M ≤ 1000000000) tasks which needs to processed in sequential order one after another. The tasks do not need to be processed immediately when the servers are free. They can wait and assigned to a faster server if necessary.

Find a schedule such that the total time needed for processing all tasks is minimized.

Example

For N = 2, M = 6, T₁ = 7, T₂= 10, the optimal schedule is:

• server 1 processes task 1 and server 2 processes task 2.
• after 7 seconds, server 1 is free and task 3 is assigned to server 1.
• after 10 seconds. server 2 is free and task 4 is assigned to server 2.
• after 14 seconds. server 1 is free and task 5 is assigned to server 1.
• after 20 seconds. server 2 is free and task 6 is not assigned to server 2.
• after 21 seconds server 1 is free and task 6 is assigned to server 1.
• after 28 seconds all tasks are complete.

On other hand, if task 6 was immediately assigned to server 2 without waiting the total time would have been 30 seconds.

Input

The first line contains T (≤ 10) the number of test cases. Followed by description of each test case. An integer N number of servers and M number of tasks. The next N lines contain T_i for each server.

Output

The minimum time for completing all tasks. Use long long data type.

Example

Input:
1
2 6
7
10

Output:
28