WEIGHT1 - VEGETABLE SHOPKEEPER 1

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.

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 <= 1000

1 <= n <= 20

1 <= weight of each vegetable <= 1000

1 <= W <= 20000

Example

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 the classical version (with harder test cases): Vegetable Shopkeeper 3


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

hide comments
2014-12-18 12:07:27 Francky
Please upload images at spoj. You know how.
Please allow all languages, or explain your choice. Why not BF ?

reply by cegprakash: Images done. Reg. BF it's a troll language so I'm just trolling around with that troll language :D

Last edit: 2023-09-08 17:01:52
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.