Hide

Problem D
誕生日の記憶

Languages en ja sv

クラーキは、自分の$N$人の友達の誕生日にお祝いをしたいので、彼らの誕生日をを知りたいと思っています。 不幸にも衝突(何人かの誕生日が同じ日になること)が起こることがあります。 これではクラーキは混乱してしまうので、衝突が起こった場合は、自分が一番好きな友達の誕生日だけを覚えておくことにしました。 それぞれの友人の誕生日のリストと、クラーキがそれぞれの友人をどれだけ好きかを与えられたとき、クラーキがどの友人の誕生日を覚えているかを出力します。

入力

入力の最初の行には、友達の数である整数$N$ ($1 \leq N \leq 2\, 000$)が入っています。

その後の、$N$行はそれぞれの友人を表します。 このうち$i$番目の行には、$i$番目の友達のファーストネーム$S_ i$($S_ i$は、$1$文字から$10$文字の間の文字列)と、クラーキがその友達をどれだけ好きかを表す整数$C_ i$ ($0 \leq C_ i \leq 100,000$)と、DD/MMという形式で誕生日が与えられています(ここで、DDは、0131の間の日、MMは、0112の間の月です)。 $C_ i$の値が大きいほど、クラーキはその友達のことが好きだということを表します。

誕生日は、2020年(うるう年)中の実在の日付です。例えば、2月28日は「28/02」です。 すべての名前は、先頭が大文字(A-Z)、以降が小文字(a-z)で構成されます。 すべての$C_ i$は異なる値です。

出力

最初の行に、整数$K$を出力します。これは、クラーキが誕生日を覚えている友人の人数です。

以降の$K$行に、それぞれ1人ずつ、選ばれた友人のファーストネームを辞書順で出力します。

採点

あなたのソリューションは、いくつかのテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功する必要があります。

グループ

ポイント

制限

$1$

$30$

$N \leq 100$

$2$

$70$

No further constraints

サンプルの説明

最初のサンプルでは、SannaとSimonの誕生日が同じです。 クラーキはSimonよりSannaの方が好きなので($1 < 2$)、SimonとSagaの誕生日しか覚えていません。

2つ目のサンプルでは、クラーキは本当に運が悪く、半分の友人の誕生日を忘れてしまいます。

サンプル入力 1 サンプル出力 1
3
Sanna 1 16/03
Simon 2 16/03
Saga 3 14/10
2
Saga
Simon
サンプル入力 2 サンプル出力 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