Greatest Hits!

Yesterday, Professor Calamaro read in the news that there were rumors about a possible comeback of Soda Stereo, a famous South American rock group. Although Soda Stereo was a well known group of the late ‘80s, Professor Calamaro had never before heard of them. He decided to go to the nearest music store to buy some of their greatest hits collections. When he arrived to the music store, he found that there were many different greatest hits CDs. Because he didn’t know any of their songs, he decided to spend a certain ammount of money to buy a couple of them so that he could listen as many songs as possible. There were two main problems, however: (1) it could be that the money was not enough to buy all the CDs, and (2) many of the CDs have the same songs over and over again. At that moment, he realized that it would be very useful for his purposes to have a program to decide which CDs to buy so that, altogether, he could maximize the number of non-repeated songs with the money budget that he has. If there were two choices that give the highest possible number of songs, he would prefer the cheapest one. And if two choices give the highest number of songs and both cost the same, the one that has one older CD (that the other does not have) should be preferred. Your task is to develop that program. Input The first line contains N > 0, the number of cases to analyze. The N cases come in the following lines. Each case is a block describing a possible scenario: • One line with the Professor’s Calamaro budget, an integer value B, 0 < B < 1000. • The CD descriptions (at least one description, but no more than 20 of them). Older CDs are listed first. • Each CD with M (0 < M < 50) songs is described with M +2 lines: one line with the name of the CD, M lines with the names of the songs (one line, one song) and one last line with an integer value c (0 < c < 100), the CD ́s cost. • Names of CDs and song ́s titles are character strings of a non–zero length with no more than 80 ASCII characters. Money values are given as numerical strings preceded by a ‘$’ sign. There is not a song title, nor a CD name that may be understood as an ammount of money. There are no two CDs with the same name. Output The output for every scenario begins with a line containing ‘Scenario #i:’, where i is the number of the scenario (numbering starting at 1), followed by a blank and the total number of non–repeated songs he can afford. Then there is a line for each one of the CD names that Professor Calamaro should buy. The names of the CDs to buy are listed from the oldest one to the newest one. At the end of that there is a blank line. Sample Input 2 $10 COMFORT Y MUSICA

2/2 En la ciudad Un misil Pasos Entre canibales $5 EL ULTIMO CONCIERTO Disco eterno Planeador Pasos $7 $60 TIT1 1 2 $25 TIT2 2 1 3 $35 TIT3 5 2 4 2 $20 Sample Output Scenario #1: 4 COMFORT Y MUSICA Scenario #2: 5 TIT2 TIT3