WEIGHT3 - VEGETABLE SHOPKEEPER 3

no tags 

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


hide comments
little_ap: 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

ssunitk: 2017-05-22 09:44:34

Easy one,little trick with [spoiler]

Last edit: 2017-08-02 13:15:20
vengatesh15: 2017-02-20 13:21:39

easy one :-)

asgupta_spoj: 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

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