Setting

The mail clerk for Sirius Cybernetics just received a new postal scale which will display the cost (in cents) to send a given parcel. The postal scale is medium duty, and will only handle parcels requiring up to $29.99 in postage. She has requested you to write a program that will convert the postage into the number of stamps needed to cover the required postage such that the cost is minimized.

The mailroom stocks up to ten different types of stamps, and only ten stamps will fit on any given parcel.

Input

For each dataset, your program would read in a number \(N\), indicating the number of different stamps. The next line contains the list of stamp values stocked by the mailroom (all separated by single spaces) followed by a sequence of amounts to convert (one amount per line) ended by a \(0\). If it is impossible to reach the given amount exactly, you are to exceed the amount by as little as possible. If there are many sets of stamps that cover the amount for the same cost, you should pick the set with the least number of stamps. If there is still a tie, choose the stamps as expensive as possible.

A value of \(N = 0\) indicates the end of the input.

Output

Output for each dataset should consist of the given stamp values on a single line (in increasing order) followed by a blank line, then, for each amount given, the amount that needs to be covered on a single line, followed by the stamps needed for the coverage on the next line (in non-increasing order), followed by a blank line. (So the last line of stamp values in the output is followed by one blank line, used to separate different datasets). All numbers are separated by single spaces.

If no solution exists, print NO SOLUTION EXISTS.

Sample Input

7
2 7 14 17 22 63 98
72
86
143
5
0
6
16 7 6 5 4 3
18
0
0

Sample Output

STAMP VALUES 2 7 14 17 22 63 98

AMOUNT 72
STAMPS USED 63 7 2

AMOUNT 86
STAMPS USED 63 14 7 2

AMOUNT 143
STAMPS USED 63 63 17

AMOUNT 5
STAMPS USED 2 2 2

STAMP VALUES 3 4 5 6 7 16

AMOUNT 18
STAMPS USED 7 7 4

This is challenge 266 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (1 vote)
Average test runtime 0.19
Points (changes over time) 10
Tried by 2 users
Solved by 1 user

Global ranking

# Name Runtime Points worth
1 AlexanderP 0.19 10