Problem J
Grand Combat Delusion: The Movie

Mynd fengin af commons.wikimedia.org

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\le n,m\le {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\le h,d\le {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\le c_i\le {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\le h_i\le {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.

3 3
5 6
1 -1 1
9 9 9

Of audvelt!

3 3
5 2
1 -1 1
9 9 9

Of erfitt!

5 1
1 9
-9 4 -3 2 -4
1

-8 er matulegt