Problem X
Tölvuíhlutir
Languages
en
is
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
Hópur |
Stig |
Takmarkanir |
1 |
20 |
$1 \leq n \leq 1\, 000$, engir tveir íhlutir eru af sömu gerð |
2 |
20 |
$1 \leq n \leq 1\, 000$, geta sérhvers íhlutar er mest $100\, 000$ |
3 |
20 |
$1 \leq n \leq 1\, 000$, $k = 1$ |
4 |
20 |
$1 \leq n \leq 1\, 000$ |
5 |
20 |
$1 \leq n \leq 100\, 000$ |
Sample Input 1 | Sample Output 1 |
---|---|
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 |
Sample Input 2 | Sample Output 2 |
---|---|
4 2 1000000 CPU QPU CPU 200000 1000 CPU 300000 1200 CPU 400000 1500 QPU 1000000000 1 |
O nei! |