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 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 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.

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

hide comments
feodorv: 2021-02-21 11:51:12

https://latex.codecogs.com/gif.download?%5C%5C%20T%20%5Cleq%2010%20%5C%5C%20N%20%5Cleq%2020%20%5C%5C%20M%20%5Cleq%202%20%5Ctimes%2010%5E%7B10%7D%20%5C%5C%20A_%7Bi%7D%20%5Cleq%2010%5E%7B9%7D

[NG]: Fixed the statement, thanks.

Last edit: 2021-02-21 15:50:15
David: 2021-02-04 18:07:21

Equation show "Invalid Equation".

limon_88: 2019-04-27 13:55:55

Nice problem @sabbir vai

wisfaq: 2017-12-12 12:11:49

@nadstratosfer:
N<=40 would have made for a better problem, imho.

Last edit: 2017-12-12 12:13:04
nadstratosfer: 2017-12-09 16:49:03

You probably got the correct approach right away, going by the status most people don't. I've been somewhat flabbergasted about what changes to my code resulted in bettering the runtime, but I see it as a plus. It's a tricky problem, a welcome change from CPP-with-fast-IO-or-TLE type ones from the same genre that keep getting added here.

Piyush Kumar: 2017-12-09 16:15:37

I am not sure if this belongs to the classical section.

morass: 2017-12-04 13:09:10

Good day to you,

Even though it is well understandable as it it, I'm convinced the "K" shall be replaced by "M" (or vice versa) :P

Good Luck & Have Nice Day!


Added by:sabbir
Date:2017-12-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All