## TAKIN - Taskin and apple tree

no tags

Taskin has an apple orchard . Every morning he goes to pick apples from orchard. He has a basket which can carry not more than K 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 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 a1 a2 a3 . . . an where ai is the number of apples in the i-th tree.

$\\&space;T&space;\leq&space;10&space;\\&space;N&space;\leq&space;20&space;\\&space;M&space;\leq&space;2\times&space;10^{10}&space;\\&space;A_{i}&space;\leq&space;10^{9}$

### Output

Print an integer the maximum number of apples

### Example

Input:25 62 1 2 7 85 101 2 4 4 6

Output:510