WEIGHT3 - VEGETABLE SHOPKEEPER 3

The cost of the vegetables is directly proportional to its weight. The vegetable shopkeeper wants to minimize the loss and maximize his profit.

At first, the customer picks n number of vegetables with their sum of weight >= target weight. This is given as input.

Then the shopkeeper can choose any combination of the vegetables picked by the customer. But the sum of weight must remain >= target weight.

The shopkeeper is experienced enough to estimate the weight of any vegetable by looking at it.

Given the target weight and the individual weights of all the vegetables, find the minimum weight loss for the shopkeeper.

weight loss = sum of weight of vegetables chosen by shopkeeper - target weight.

Input

The first line consists of an integer t, the number of test cases. For each test case the first line consists of two integers n and W, the number of vegetables picked by the customer and the target weight respectively. The next line consists of n integers denoting the weights of each vegetable.

Output

For each test case, find the minimum weight loss for the shopkeeper.

Constraints

1 <= t <= 100

1 <= n <= 100

1 <= weight of each vegetable <= 1000

1 <= W <= 50000

Sample

Input
3
3 40
20 15 15
5 24
5 9 7 10 10
4 40
20 15 15 8

Output
10
0
3

See also tutorial version (easy test cases): VEGETABLE SHOPKEEPER 1


Added by:cegprakash
Date:2016-11-18
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

hide comments
2020-09-03 18:17:54
why is my input always a null value?
I did it on my personal compiler, but it worked fine
2017-05-22 09:44:34
Easy one,little trick with [spoiler]

Last edit: 2017-08-02 13:15:20
2017-02-20 13:21:39
easy one :-)
2016-12-11 12:56:33
easy , just need to take care of [SPOILER] and a little bit trick is also involved.

Last edit: 2017-01-17 04:31:21
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.