Thief's Dilemna

Background:

A thief is trying to steal some items from a rich palace. The thief wants to maximize what he takes out, but he only has a limited amount of space to carry things with. your mission is to help him maximize the amount he takes out.

Input:

the first couple of lines will describe the items he can take. Each line is of the form:

value space

where value is the value of the item, and space is the number of spaces it takes up in the thief's bag. (For simplicity, we'll assume everything is one dimensional). The first item is item 'A', the second 'B', and so on. This section is ended by a line containing only $END There will be no more than 10 items.

Following the $END will be a number of cases. Each case is just a number representing the number of spaces the thief has available in his bag.

Output:

For each test case, you have to print the maximum value the thief can take out, and what items to grab. The format should be:

max item,item,...

where max is the max value the thief can get, and item,item,... are the names of the items to be taken. The list should be sorted alphabetically. The last item should not be followed by a comma. If no items can be taken, then just print a 0 and list no items. For obvious reasons, no item can be included more than once.

Sample Input:

15 10
3 30
5 4
100 3
90 100
5 3
5 6
5 9
$END
2
50
300

Sample Output:

0
135 A,C,D,F,G,H
228 A,B,C,D,E,F,G,H