There are N (1 ≤ N ≤ 100000) servers and each has a fixed serving time Ti 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, T1 = 7, T2 = 10, the optimal schedule is:

• server1 processes task1 and server2 processes task2.
• after 7 seconds, server1 is free and task3 is assigned to server1.
• after 10 seconds. server2 is free and task4 is assigned to server2.
• after 14 seconds. server1 is free and task5 is assigned to server1.
• after 20 seconds. server2 is free and task6 is not assigned to server2. It waits for 1 second.
• then after 21 seconds server1 is free and task6 is assigned to server1.
• After 28 seconds all tasks are completed.
• On other hand, if task6 was immediately assigned to server2 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 Tk 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