Problem N
Ævintýraröð
Languages
en
is
Jörmunrekur var að skoða gamla uppáhalds tölvuleikinn sinn DeceitfulLOAM og uppgötvaði að ekki aðeins væri hann orðinn úreltur heldur það væru komnar þrjár nýjar útgáfur til viðbótar, þar af eru tvær þeirra einnig úreltar og önnur þeirra risin aftur frá dauðum! Hann sættir sig við einhverjar breytingar, en ekki svo mikið. Hann prófar að spila næstu útgáfu á eftir henni sem hann spilaði á sínum tíma, sem er núna þekkt sem Glyphplane Classic. Hann les sér aðeins til um breytingarnar og kemst að því að í þessarri útgáfu er búið að bæta við ýmsum ævintýrum sem hækka reynslugildi spilarans að þeim loknum. Við þetta fer heilinn hans Jörmunreks á fullt.
Verðlaunin virka sem svo að því meiri reynslu sem spilarinn er með, því meiri fá þeir að ævintýri loknu. Nánar tilekið er hvert ævintýri með gildi $a$ og $b$ þannig að ef spilarinn er með reynslugildi $x$ fyrir lok ævintýrisins fá þeir $ax + b$ reynslu til viðbótar. Þetta þýðir að reynslugildi þeirra eftir ævintýrið sé þá $x + ax + b$. Jörmunrekur vill auðvitað hækka þessi gildi með sem skilvirkasta hætti, svo í hvaða röð ætti hann að klára ævintýrin?
Inntak
Fyrsta línan inniheldur tvær heiltölur $n$ og $x$, fjölda ævintýra og upphaflegt reynslugildi Jörmunreks í leiknum, þar sem $0 \leq x \leq 1\, 000$. Næst fylgja $n$ línur, hver lýsir einu ævintýri. Hver lína byrjar á nafni ævintýrisins, svo koma heiltölurnar $a$ og $b$ á eftir, þar sem $0 \leq a, b \leq 1\, 000$, allt aðskilið með bilum. Nöfnin innihalda bara enska há- og lágstafi og eru mest $20$ stafir að lengd. Heildarlengd allra nafna í inntaki er mest $300\, 000$ stafir. Öll ævintýri munu hafa ólík nöfn.
Úttak
Skrifaðu út nöfnin á ævintýrunum í þeirri röð sem Jörmunrekur ætti að klára þau, þannig að ævintýrið sem á að gera fyrst sé prentað fyrst. Prenta skal hvert nafn á eigin línu. Ef til er meir en eitt rétt svar eru öll rétt svör tekin gild.
Stigagjöf
Hópur |
Stig |
Takmarkanir |
1 |
20 |
$1 \leq n \leq 2$ |
2 |
20 |
$1 \leq n \leq 8$ |
3 |
20 |
$1 \leq n \leq 50$ |
4 |
20 |
$1 \leq n \leq 500$ |
5 |
20 |
$1 \leq n \leq 10^5$ |
Sample Input 1 | Sample Output 1 |
---|---|
8 0 CooksAssistant 50 250 SheepShearer 25 125 RestlessGhost 62 500 ImpCatcher 100 375 VampireSlayer 150 325 DoricsQuest 75 175 GoblinDiplomacy 15 125 SeaSlug 200 175 |
GoblinDiplomacy RestlessGhost CooksAssistant SheepShearer ImpCatcher DoricsQuest VampireSlayer SeaSlug |
Sample Input 2 | Sample Output 2 |
---|---|
3 100 YouGetNothing 0 0 NoScaling 0 100 NoConstant 100 0 |
YouGetNothing NoScaling NoConstant |
Sample Input 3 | Sample Output 3 |
---|---|
2 1 A 1 4 B 2 9 |
B A |