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 picks the apples, and puts them into the basket. Taskin goes to each tree and either picks 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 test cases.

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¹⁰
A_i ≤ 10⁹

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