Problem J
Grand Combat Delusion: The Movie
Languages
en
is
Bardagarnir virka alveg eins og í Grand Combat
Delusion. Sem sagt, Matt og félagar byrja alltaf. Þeir
gera skaða sinn á óvininn og ef hann deyr sigra þau. Annars
gerir óvinurinn einn skaða á Matt og félaga og svo endurtekur
þetta sig. Ef Matt og félagar sigra andstæðing gera þau aftur
fyrst þegar þau berjast við næsta andstæðing. Eins og áður mun
útbúnaður sem kostar $c$
hækka skaða Matt og félaga um $c$. Þar sem það eru álög á sumum
útbúnaði getur hann kostað neikvæðan pening (Matt og félagar fá
sem sagt borgað fyrir að taka hlutinn að sér) en að sama skapi
hefur útbúnaðurinn þá líka neikvæð áhrif á skaða Matt og
félaga.
Eina lokaflækjustigið á þessu öllu saman er að búðareigandinn sem selur útbúnaðinn er afar sérvitur og vill endurraða vöruhillunum sínum sem minnst. Hann er búinn að raða öllum útbúnaðinum upp í eina röð á eina hillu og vill aðeins selja samfellt bil af hlutum. Sem sagt ef Matt og félagar kaupa tvo mismunandi hluti þurfa þau einnig að kaupa alla hluti þar á milli á hillunni. Leyfilegt er að kaupa ekkert.
Inntak
Fyrsta lína inntaksins inniheldur tvær jákvæðar heiltölur $n, m$ með $1 \leq n, m \leq 10^5$. Talan $n$ er fjöldi kaupa í boði og $m$ er fjöldi óvina. Næsta lína inntaksins inniheldur tvær jákvæðar heiltölur $h, d$ með $1 \leq h, d \leq 10^5$. Talan $h$ er hversu mikinn skaða Matt og félagar geta þolað áður en þau tapa og $d$ er skaðinn sem þau gera án auka útbúnaðar. Þar næst er lína með $n$ heiltölum $c_1, \dots , c_ n$ með $-10^9 \leq c_ i \leq 10^9$ þar sem $c_ i$ er verð $i$-ta hlutarins. Hlutirnir eru gefnir í þeirri röð sem þeim er raðað upp á búðarhilluna. Loks er ein lína með $m$ jákvæðum heiltölum $h_1, \dots , h_ m$ með $1 \leq h_ i \leq 10^9$ þar sem $h_ i$ er hversu mikinn skaða $i$-ti óvinurinn getur þolað áður en búið er að sigrast á honum. Óvinirnir eru gefnir í þeirri röð sem barist er við þá.
Úttak
Ef þau sigra sama hvaða útbúnaður er valinn, prentið ‘Of audvelt!’. Ef ekkert val á útbúnaði leyfir þeim að sigra, prentið ‘Of erfitt!’. Annars prentið ‘x er matulegt’ þar sem $x$ er samtals kostnaður ódýrasta mengi útbúnaðar sem leyfir þeim að sigra.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 5 6 1 -1 1 9 9 9 |
Of audvelt! |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 5 2 1 -1 1 9 9 9 |
Of erfitt! |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 1 1 9 -9 4 -3 2 -4 1 |
-8 er matulegt |
