시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

2020 년 우주 IT 인재들을 발굴, 육성하고 IT 인재들의 중요성을 인식하는 분위기 조성을 위하여 태양계의 지구 전산학 학회인 ACM(Association for Computing Machinery)에서는 대학생들을 대상으로 프로그래밍 경시대회 ACM-UCPC(Universal Collegiate Programming Contest)를 개최한다. 시간과 장소의 제약으로 인터넷 예선을 치르게 되었다.

예선을 치른 후 각 팀의 성적이 푼 문제 수와 페널티로 주어지는데, 더 많은 문제를 푼 팀이 성적 순위에서 앞서고 같은 수의 문제를 풀었을 때에는 페널티가 적은 팀이 순위에서 앞선다. 순위대로 정렬된 대회 결과가 주어졌을 때 총 60 팀을 선발하는 프로그램을 작성하시오. 단, 어떤 두 팀도 같은 순위가 없다.

성적이 우수한 팀을 뽑되 각 학교의 참여도를 높이고, 한 학교에서 너무 많은 수의 팀이 선발되는 것을 피하기 위해서 성적이 우수한 순서대로 아래 1~5 의 규칙을 적용하여 선발 혹은 탈락을 결정한다.

  1. 현재 고려하는 팀이 속한 학교에서 M 개의 팀이 참여했다면 최대 M/2 (올림)개 팀이 선발된다. 예를 들어 2 개 팀이 참여했다면 최대 1 팀이, 3 개 팀이 참여했다면 최대 2 팀이 선발된다.
  2. 현재 고려하는 팀이 전체 성적이 1 위 ~ 10 위이면, 같은 학교에서 지금까지 3 개 이하의 팀이 선발되었을 경우에만 선발된다.
  3. 현재 고려하는 팀이 전체 성적이 11 위 ~ 20 위이면, 같은 학교에서 지금까지 2 개 이하의 팀이 선발되었을 경우에만 선발된다.
  4. 현재 고려하는 팀이 전체 성적이 21 위 ~ 30 위이면, 같은 학교에서 지금까지 1 개 이하의 팀이 선발되었을 경우에만 선발된다.
  5. 현재 고려하는 팀이 전체 성적 31 위 이하이면, 같은 학교에서 지금까지 한 팀도 선발되지 않았을 경우에만 선발된다.

단, 위의 규칙대로 선발해서 60 팀을 채우지 못할 경우에는 선발되지 못한 팀들 중 성적 순위가 앞선 팀을 차례대로 선발해서 60 팀을 채운다. 참가 팀의 수가 60 팀이 안 될 때에는 모든 팀을 선발한다. 

입력

 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스 첫 줄에는 참가 팀의 수 N 이 주어지고 두 번째 줄부터 N 줄에는 팀 이름(team), 학교 이름(school), 문제를 푼 수(solved), 페널티(penalty)가 공백을 하나 사이에 두고 주어진다(1 ≤ N ≤ 1000, 1 ≤ solved ≤ 10, 1 ≤ penalty ≤ 10000, team 과 school 은 공백을 포함하지 않은 길이 20 이하의 문자열)

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 선발된 팀 중 전체 성적이 최하위인 팀의 이름을 한 줄에 하나씩 출력하시오. 

예제 입력 1

3
120
WindMill DonggukU. 10 799
IHS DonggukU. 10 957
KBS ChungbukNationalU. 10 2670
Guldari DonggukU. 10 3278
Durumi DonggukU. 10 3875
Humming ChungbukNationalU. 10 4491
BlueOcean DonggukU. 10 5363
Dhakerz KwangwoonU. 10 5731
Ateam YonseiU. 10 6844
ASCII_ANYWAY DonggukU. 10 6942
Jupiter KangnamU. 10 7065
academe PukyongNationalU. 10 8606
YoMyBaby PukyongNationalU. 10 9311
Bio-MAN PukyongNationalU. 10 9672
Zeropage KangnamU. 9 701
[email protected] KongjuU 9 1062
ISAAC KangnamU. 9 1492
ASCII_Run PukyongNationalU. 9 1927
Free ChosunU. 9 2056
Black_Hole ChonnamU. 9 2362
Woos KayaU. 9 4253
Run&Build_Blue HUFS 9 5610
Little_Buddha Gist 9 6001
Unlimited KyungsungU. 9 6836
Geek KayaU. 9 6942
Allage AndongNationalU. 9 7968
Codeholic HansungU. 9 8037
educom JoongbuU. 9 8274
TimeStopper HansungU. 9 8452
polaris ChonbukNationalU. 8 147
WonderWomen DonggukU. 8 358
pietta KyonggiU. 8 1175
GG!! Gist 8 1359
SangjiCSE MokwonU. 8 2916
USB CUK 8 3208
Taurine-MAN EwhaWomansU. 8 4339
DAU Chung-AngU. 8 4376
Nothing! KoreaMaritimeU. 8 5065
NaturalSelection HanyangU. 8 5895
SecuLock GJU 8 5935
P.L.A WoosongU. 8 6712
Hackers DongyangU. 8 6749
Falcon GJU 8 8139
MP3 ICU 8 8144
AM7 KyungpookNationalU. 8 8216
Dunhill HanbatU. 8 8783
Mouse KangnungU. 8 9055
PLUM SoongsilU. 7 688
Waytogo KyungHeeU. 7 1707
Sherbet ICU 7 3093
Flamingo-knights EwhaWomansU. 7 5376
One.shot SNUT 7 8217
ZZang KookminU. 7 8394
JustForFun SejongU. 7 8541
Anyway KyonggiU. 7 8650
smalleyes Chung-AngU. 7 8969
BrainKorea DongaU. 7 9127
HelloWorld KangnungU. 6 2478
pknu ChosunU. 6 3237
WANT HanyangU. 6 4678
CodeGura AjouU. 6 5982
EDUCOM06 KoreaMaritimeU. 6 7798
POCS-2 KAIST 6 8398
A.C.E JoongbuU. 6 8960
K HanbatU. 6 9369
Kiss DongseoU. 6 9626
Solution MokwonU. 5 636
goto HandongU. 5 1640
Template HannamU. 5 1725
BLUE AndongNationalU. 5 2247
SUNFLOWER HannamU. 5 2797
Great KoreaU. 5 3057
[email protected] Mju 5 4672
Transmute ChonnamU. 5 8386
Mighty InhaU. 5 8467
Cube DongaU. 5 9315
NFS SangJiU. 4 2733
Nippy-Crew Mju 4 4466
slgijung SemyungU. 4 4690
Enigma InjeU. 4 4809
SNUcker U.ofSeoul 4 6714
Becaution SeoulNationalU. 4 7268
Excalibur InjeU. 4 7809
POCS-1 HanKukAviationU. 4 8051
Impression POSTECH 3 1188
Lineage ChungbukNationalU. 3 1362
COCOA KyungsungU. 3 4895
IamYourFather HUFS 3 5729
NoBreak!! KyungHeeU. 3 5964
Haroobang SogangU. 3 6421
Oblivion CNU 3 7257
P.C.R.C. PUFS 3 8552
KIN~2 PusanNationalU. 3 8926
Run&Build_Red Tu 2 43
Genesis KyungpookNationalU. 2 1258
[email protected] PCU 2 1308
Fluke AjouU. 2 1453
VITA5000 KNIT 2 3264
Challangers ChejuNationalU. 2 3602
POCS-3 KonkukU. 2 3946
HEUM DongseoU. 2 4487
Colossus ChonbukNationalU. 2 5025
Gag-MAN KongjuU 2 5654
Posis DongyangU. 2 5944
H-COPS KwangwoonU. 2 6156
SOCG YeungnamU. 2 7232
again2002 Dju 2 7959
KoreaCBNU CUK 2 8242
Alchemist HallaU. 2 8516
lupin1 HongikU. 2 8654
Random Dju 2 8762
wanna_accepted KAIST 2 9556
GuriGuri KangwonNationalU. 2 9761
NeverAC UidukU. 1 3300
M4A1 ChejuNationalU. 1 5293
lupin2 HallaU. 1 5552
A.C.E2 DongEuiU. 1 5804
STOC HongikU. 1 6096
MULP SillaU. 1 6590
LoBC KangnamU. 1 9636
130
COCOON KyonggiU. 10 954
SSG_Wanna_Be KonkukU. 10 2096
Transmute KyonggiU. 10 2448
Nothing! KyonggiU. 10 2872
Template KyonggiU. 10 2898
Kaist KyonggiU. 10 3453
Little_Buddha KyonggiU. 10 4235
ISAAC KyonggiU. 10 4813
Jupiter KyonggiU. 10 5132
ACceptMessage KyonggiU. 10 5261
KDDR HannamU. 10 5311
Hackers Gist 10 5331
again2002 JoongbuU. 10 6770
CK2 Gist 10 6792
ASCII_ANYWAY InhaU. 10 9073
PRIME Gist 10 9085
Run&Build_Blue HannamU. 10 9809
[email protected] InhaU. 10 9813
DAU Gist 9 640
Seed EwhaWomansU. 9 642
MIRACLE AjouU. 9 1167
POCS KangwonNationalU. 9 1536
Y.S.J. ChosunU. 9 4529
Mighty DonggukU. 9 6094
IamYourFather GJU 9 6962
Old&New KAIST 9 8623
IHS KyungsungU. 9 8653
Geek KonkukU. 9 8900
ASCII_Run PCU 9 9653
KoreaCBNU KangnamU. 8 1411
mirgachi3 KangwonNationalU. 8 1941
ZZang KangnamU. 8 2301
ALPS-II AjouU. 8 4027
POCS-1 DongseoU. 8 4556
KartRider KonkukU. 8 5037
POCS-3 DongEuiU. 8 5456
smalleyes KyungHeeU. 8 5911
VITA5000 ChonnamU. 8 6381
Great DongseoU. 8 6435
WANT KoreaMaritimeU. 8 6605
Free KongjuU 8 8380
ForElise KangwonNationalU. 8 8498
wanna_accepted Dju 7 1185
FOCS MokwonU. 7 3303
hycoc HanKukAviationU. 7 3925
Haroobang KyungpookNationalU. 7 4047
Falcon KyungHeeU. 7 4379
Genesis EwhaWomansU. 7 4861
WOW KangwonNationalU. 7 5233
JustForFun DonggukU. 7 5278
Posis PCU 7 5756
Buffer DongEuiU. 7 6274
Dr.Tour HannamU. 7 7031
Stardust KangnungU. 7 7227
The_One KwangwoonU. 6 604
SP3 DonggukU. 6 675
Gag-MAN JoongbuU. 6 828
Cube KangnamU. 6 2364
WonderWomen DongyangU. 6 2799
Zeropage ICU 6 2931
WaTangKa CUK 6 3045
P.L.A HannamU. 6 4214
E.S.C. JoongbuU. 6 4757
HelloWorld CNU 6 5103
CodeGura KangwonNationalU. 6 5827
Anyway KangwonNationalU. 6 8353
BlueOcean KongjuU 6 9263
AlphaNumbers HUFS 6 9969
Tclab KAIST 5 241
[email protected] CNU 5 1510
SECOM HandongU. 5 2186
YoMyBaby EwhaWomansU. 5 3361
Bagle KwangwoonU. 5 3437
asdf DongyangU. 5 4031
Al-Pain Dju 5 5811
Random HannamU. 5 6259
KeyMaker DongseoU. 5 6790
UP Dju 5 7369
SUNFLOWER KoreaU. 5 7765
AlgorithmZ ChonbukNationalU. 5 8371
Woori MokwonU. 5 8467
GIRLS EwhaWomansU. 5 9009
lupin2 KangwonNationalU. 5 9990
pets KwangwoonU. 4 609
Unlimited HannamU. 4 708
zraler-1 MokwonU. 4 1275
Accepted2 HUFS 4 1335
Reloaded PCU 4 2028
BrainKorea HanyangU. 4 2283
BLUE HannamU. 4 2426
EAGLES KonkukU. 4 3543
Chaos KyungHeeU. 4 4134
Zenith KayaU. 4 5020
TimeStopper DongEuiU. 4 6881
SODA ChejuNationalU. 4 7326
NULL KyungHeeU. 4 7343
SOCG KangnamU. 4 8762
ENIAC KyungpookNationalU. 3 568
KANG KookminU. 3 1132
Bio-MAN Mju 3 2438
KU-LALA~ KyungsungU. 3 2847
POCS-2 KoreaU. 3 3901
stepbystep KyungpookNationalU. 3 6522
A.C.E2 KayaU. 3 6971
[email protected] KyungsungU. 3 7574
Kiss DonggukU. 2 26
WindMill ICU 2 453
Oblivion KNIT 2 528
Colossus KoreaMaritimeU. 2 1343
COCOA Gist 2 3068
Pholic MokwonU. 2 3254
Waytogo KAIST 2 3965
Black_Hole KangnamU. 2 7212
Ateam ChosunU. 2 8402
MVP HanbatU. 2 8473
Taurine-MAN KangnungU. 2 8894
TNB KyungHeeU. 2 9036
One.shot Dju 1 2172
Weird-OS CNU 1 2229
MONG PCU 1 2441
Alchemists KookminU. 1 3042
lupin1 HansungU. 1 3912
Sherbet HanyangU. 1 5228
countdown MokwonU. 1 5360
MP3 ChejuNationalU. 1 6227
P.C.R.C. HansungU. 1 6916
Solution ChejuNationalU. 1 7028
SLL KNIT 1 7700
Flamingo-knights AjouU. 1 9333
GuriGuri Mju 1 9517
50
Random ChungbukNationalU. 10 1159
POCS GJU 10 5069
Sherbet HandongU. 10 6524
EDUCOM06 ChejuNationalU. 10 7516
ArmBar DongseoU. 10 8744
RM-RF/ CUK 10 9670
Mighty GJU 9 2098
MONG Gist 9 2423
pknu InjeU. 9 3162
IamYourFather ICU 9 5403
Waytogo DongEuiU. 9 6208
MULP DongEuiU. 9 6378
Marcie DongseoU. 9 6736
again2002 Dju 9 7733
COCOA CNU 9 8537
AlgorithmZ InjeU. 9 8947
KeyMaker ChungbukNationalU. 9 9841
hycoc HanbatU. 8 1040
GIRLS AndongNationalU. 8 1077
ZZang HanKukAviationU. 8 5419
[email protected] Chung-AngU. 8 6310
stepbystep Dju 8 8618
Zraler CUK 8 9264
Anyway EwhaWomansU. 7 350
Taurine-MAN AndongNationalU. 7 730
ACceptMessage CUK 7 1543
SECOM DonggukU. 7 2556
Colossus ChungbukNationalU. 7 6538
Arirang Dju 6 1925
[email protected] DongEuiU. 6 2819
AlphaNumbers HongikU. 6 2868
slgijung ChejuNationalU. 5 437
ENIAC GJU 5 1155
zraler-2 CNU 5 1375
E.S.C. DongyangU. 5 5947
NoBreak!! ChonbukNationalU. 5 7958
PaperBox DongEuiU. 5 8861
[email protected] HanbatU. 5 9398
Bagle ChonbukNationalU. 4 9701
OTL Chung-AngU. 3 4008
Bio-MAN ChosunU. 3 4015
HelloWorld HannamU. 3 7572
EAGLES ChungbukNationalU. 2 2322
Chaos HansungU. 2 5969
CodeGura ChungbukNationalU. 2 7350
MP3 ChonbukNationalU. 2 8172
TNB DongseoU. 1 416
Kiss CUK 1 2741
SUNFLOWER DonggukU. 1 3758
USB HongikU. 1 9459

예제 출력 1

Oblivion
lupin1
USB