WEIGHT1 - VEGETABLE SHOPKEEPER 1

no tags 



The cost of the vegetables is directly proportional to it's 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.


Input Constraints:

1 <= t <= 1000

1 <= n <= 20

1 <= weight of each vegetable <= 1000

1 <= W <= 20000


Sample Input:

3

3 40

20 15 15

5 24

5 9 7 10 10

4 40

20 15 15 8


Sample Output:

10

0

3

 

See also classical version (hard test cases): VEGETABLE SHOPKEEPER 3


hide comments
Francky: 2014-12-18 12:07:27

Please upload images at spoj. You know how.
Please allow all languages, or explain your choice. Why not BF ?


Added by:cegprakash
Date:2014-11-04
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC BF C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET