Taskin has an apple orchard Every morning he goes to pick apples from orchard. He has a basket which can carry not more than M apples. Taskin pick apples, and put them into the basket. Taskin goes to each tree and either pick all the apples from that tree or skips that tree.

What is the maximum number of apples taskin can pick.

Input

In the first line there will be an integer T number of testcases.

For every test case there will be 2 integers in the first line N and M, number of apple tree in the orchard and capacity of basket respectively.

Next line contains N integers a₁ a₂ a₃ a_n where a_i is the number of apples in the i-th tree.

T <= 10
N <= 20
M <= 2 * 10^10
Ai <= 10^9

Output

Print an integer, the maximum number of apples.

Example

Input

2
5 6
2 1 2 7 8
5 10
1 2 4 4 6

Output

5
10