Problem X
Tölvuíhlutir

Mynd fengin af commons.wikimedia.org

Magni er að fjárfesta í nýrri borðtölvu og þá kemur að því mikilvæga atriði að skipuleggja hvaða íhluti ætti að kaupa til að mynda borðtölvuna. Hann er auðvitað ekki með óendanlegt fjármagn, svo flækjan felst í því að fá sem bestu tölvuna fyrir þann pening sem hann hefur. Í raunheiminum eru auðvitað mismunandi íhlutir misgóðir í ólík verk, en til einföldunar munum við líta á meðalgetu hvers íhluts. Ef hann kaupir mjög dýrt og flott skjákort, en mjög slappan örgjörva mun skjákortið ekki geta notið alla sína getu. Heildargeta tölvunnar ákveðst af lélegasta íhlutnum. Getur þú hjálpað Magna að eignast sem bestu tölvuna?

Inntak

Fyrsta línan inniheldur þrjár jákvæðar heiltölur $n, k$ og $p$, þar sem $n$ er fjöldi íhluta í boði, $k$ er fjöldi tegunda íhluta og Ávallt gildir að $1 \leq k \leq n$. Gildið $p$ er hversu mikinn pening Magni hefur til að spreða í borðtölvu, það uppfyllir $0 \leq p \leq 10^9$. Næsta lína inniheldur $k$ strengi með nöfnum íhlutategundanna, aðskilin með bilum. Næstu $n$ línur munu hver lýsa einum íhlut. Hver slík lína inniheldur streng $s$ og tvær heiltölur $v, g$. Strengurinn lýsir tegund íhlutsins og er ávallt einn þeirra $k$ sem komu fyrir ofar í inntaki. $v$ lýsir verði íhlutsins og uppfyllir $0 \leq v \leq 10^9$. Loks lýsir $g$ getu tölvunnar ef þessi íhlutur er settur í tölvuna og uppfyllir $0 \leq g \leq 10^9$. Tölvan þarf að innihalda nákvæmlega einn íhlut af hverri tegund og er þá geta tölvunnar lægsta geta þessarra $k$ íhluta.

Allir strengir í inntaki eru mest $10$ stafir að lengd og innihalda aðeins enska há- og lágstafi. Heildarlengd allra strengja í inntaki verður mest $6 \cdot 10^5$ stafir.

Úttak

Prentaðu getu bestu tölvunnar sem Magni getur eignað sér fyrir peninginn sem hann hefur. Ef peningurinn dugar ekki til að kaupa neina tölvu prentaðu í staðinn O nei!.

Stigagjöf

10 6 350000
Board CPU GPU RAM Supply Drive
Board 20000 2000
CPU 90000 1100
CPU 120000 1200
GPU 100000 1100
GPU 150000 1300
RAM 15000 750
RAM 25000 1250
Supply 20000 750
Supply 30000 1300
Drive 10000 2000

1100

4 2 1000000
CPU QPU
CPU 200000 1000
CPU 300000 1200
CPU 400000 1500
QPU 1000000000 1

O nei!