E: 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.
The first line contains N > 0
The output for every scenario begins with a line containing ``Scenario #i
Output
Sample Input
2
$10
COMFORT Y MUSICA
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