Hide

Problem J
Grand Combat Delusion: The Movie

Languages en is
/problems/hi.grandcombatdelusionthemovie/file/statement/is/img-0001.png
Mynd fengin af commons.wikimedia.org
Þó klukkan sé orðið margt er ákveðið að bæta við einni mynd enn. Næsta mynd sem verður fyrir valinu er Grand Combat Delusion: The Movie, mynd upp úr vinsæla tölvuleiknum Grand Combat Delusion. Eins og í tölvuleiknum þurfa aðalkarakterarnir nú að safna sér betri útbúnaði til að geta sigrast á óvinum sínum. Nú hafa fleiri bæst við í teymi aðalkaraktera og bendir ein þeirra, Anna, á þá skemmtilegu staðreynd að sniðugt gæti verið að notast við fleiri en einn hlut. Með þetta í huga kemur aftur að því að velja sér ódýrasta útbúnaðinn sem dugar samt. Þar sem Matt og félagar eru ekki sérstaklega tölvunarfræðilega þenkjandi velja þau bara eitthvað sem lítur vel út. Getur þú gert betur?

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