BURGLARY - Boat Burglary

Rachid lives on a boat, and owns only a few items, n to be precise. He takes big care of his items, and measured the weight of each of them with high precision. Item i weights Wi micrograms. One night a thief visits his boat and steels some items. Rachid notices that the next morning, because the boat is lighter, and he could measure from the water level that this difference is D micrograms. He would like to know how many items are missing, just by examining these weights, and asks you for help.

Input

The first line of the input consists of the number of test cases, T. T test cases follow. Each case consists of two lines, the first one containing two integers N and D, separated by a space. Then second line contains n integers, representing the weights of all items, separated by space.

The input satisfies the following limits.

1 ≤ T ≤ 20
1 ≤ N ≤ 30
0 ≤ D ≤ 3*1010
0 ≤ Wi ≤ 109

Output

For each test case output one line containing "Case #x: y", where x is the case number (starting from 1). If the number of missing items could be determined, then y is this number. If there are several answers to the problem y is the string "AMBIGIOUS" and if there is no answer y is the string "IMPOSSIBLE" (quotes added for clarity and are not part of the output).

Example

Input:
4
5 10
2 3 6 9 5
5 20
1 4 2 3 15
5 20
1 4 5 15 27
5 16
1 2 4 8 32

Output:
Case #1: 3
Case #2: 3
Case #3: AMBIGIOUS
Case #4: IMPOSSIBLE	

Added by:xtof
Date:2016-10-06
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:http://acm.tju.edu.cn/toj/showp4095.html

hide comments
2021-08-15 09:49:42
Input:
4
5 10
2 3 6 9 5
5 20
1 4 2 3 15
5 20
1 4 5 15 27
5 16
1 2 4 8 32

Output:
Case #1: 3
Case #2: 3
Case #3: AMBIGIOUS
Case #4: IMPOSSIBLE
I think Case #2 should be AMBIGIOUS, right? We have 2 choices: 1 4 15 and 2 3 15
2018-05-25 08:30:04
It should be AMBIGUOUS instead of AMBIGIOUS.
2016-11-03 09:58:11 wisfaq
Anybody out there ? Why don't I get an answer on a reasonable request?

@xtof: thanks for raising the limit.

Last edit: 2016-11-17 10:01:17
2016-10-21 21:31:00 wisfaq
Would it be possible to raise the time limit to say 2 or 4 sec to make it possible that slow languages like Python can get AC?

Last edit: 2016-10-21 21:32:32
2016-10-12 10:46:06 Christoph Dürr
Dear dwij28, I added the constraint on D. Indeed you can do all computations with 64 bits integers.

Dear Poog and abhi2296,
try to generate an instance with N=30, Wi=uniform random chosen integers among [0, 10^9] and D the sum of the first 15 among those numbers. Will your code run correctly on it?

2016-10-11 11:54:36 Poog
My code, is running on Ideone.com (and get the right answer), but here i get SIGABRT on runtime, any hints?
2016-10-08 20:06:27 :D
I assumed it fits into signed 64b integer.
2016-10-08 15:54:02
What is the constraint on D ?

Last edit: 2016-10-08 17:58:15
2016-10-07 21:09:45 :D
It's working now, thanks.
2016-10-07 16:56:37 Christoph Dürr
Sorry for that, it should be fixed now.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.