Problem M
Ævintýraröð

Mynd fengin af commons.wikimedia.org

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

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

3 100
YouGetNothing 0 0
NoScaling 0 100
NoConstant 100 0

YouGetNothing
NoScaling
NoConstant

2 1
A 1 4
B 2 9

B
A