Hide

Problem D
Födelsedagsmemorisering

Languages en ja sv

Krarkl vill lära sig alla sina $N$ kompisars födelsedagar utantill, så att han varje dag vet vem han ska gratta. Tyvärr så uppstår det ofta krockar, det vill säga flera kompisar som fyller år på samma dag. Det här gör Krarkl förvirrad, så han bestämmer sig för att för varje datum som har en krock bara komma ihåg födelsedagen för den kompis han tycker mest om. Givet en lista med födelsedagen för varje kompis och hur mycket Krarkl tycker om kompisen, skriv ut vilka kompisar Krarkl kommer minnas födelsedagen för.

Indata

Den första raden i indata innehåller heltalet $N$ ($1 \leq N \leq 2\, 000$), antalet kompisar.

Sedan följer $N$ rader, en för varje kompis. Den $i$:te raden består av en sträng med den $i$:te kompisens förnamn, $S_ i$ ($S_ i$ är mellan $1$ och $10$ tecken lång), ett heltal $C_ i$ ($0 \leq C_ i \leq 100\, 000$) som säger hur mycket Krarkl gillar kompisen samt kompisens födelsedag på formatet DD/MM (där DD är en dag mellan 01 och 31 och MM är en månad mellan 01 och 12). Ett högre värde på $C_ i$ betyder att Krarkl gillar kompisen mer.

Födelsedagarna kommer att vara riktiga datum under 2020 (ett skottår), t.ex. 28/02 för den tjugoåttonde februari. Namnen kommer bestå av enbart små engelska bokstäver (a-z), med stor första bokstav (A-Z). Alla $C_ i$ kommer att vara olika.

Utdata

Du ska skriva ut en rad med ett heltal $K$, antalet kompisar vars födelsedag Krarkl kommer minnas.

Den ska följas av $K$ rader med ett ord vardera, förnamnen på de utvalda kompisarna, i alfabetisk ordning.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$30$

$N \leq 100$

$2$

$70$

Inga ytterligare begränsningar

Förklaring av exempelfall

I det första exemplet har Sanna och Simon samma födelsedag. Eftersom Krarkl gillar Sanna mindre än Simon ($1 < 2$) så kommer Krarkl bara komma ihåg Simons och Sagas födelsedagar.

I det andra exemplet har Krarkl jätteotur och komma att missa hälften av sina kompisars födelsedagar.

Sample Input 1 Sample Output 1
3
Sanna 1 16/03
Simon 2 16/03
Saga 3 14/10
2
Saga
Simon
Sample Input 2 Sample Output 2
10
Oden 78 03/12
Tor 132 14/05
Freja 10000 14/05
Loke 512 12/10
Hel 14 04/05
Fjorgynn 532 13/05
Hildegun 500 13/05
Vindsval 17 03/12
Snotra 20 04/05
Kvaser 420 03/12
5
Fjorgynn
Freja
Kvaser
Loke
Snotra