Problem K
Einvígi

Einvígi milli tveggja hermenn

Tómas er mikill aðdáandi stríðsleikja. Uppáhaldsleikurinn hans núna er Einvígi margra. Í leiknum eru tveir spilarar að spila orrustu. Hver orrusta samanstendur af mörgum einvígum.

Tómas hefur $n$ hermenn, hver táknaður með styrkleika $a_ i$. Andstæðingur Tómasar hefur einnig $n$ hermenn, hver táknaður með styrkleika $b_ i$.

Einvígin fara þannig fram að $i$-ti hermaðurinn hjá Tómasi berst við $i$-ta hermanninn hjá andstæðingi sínum. Tómas vinnur einvígið ef $a_ i > b_ i$, það er jafntefli ef $a_ i = b_ i$ og andstæðingurinn vinnur ef $a_ i < b_ i$. Einvígin fara fram í hækkandi röð; fyrst berjast $a_1$ og $b_1$, svo $a_2$ og $b_2$, og svo framvegis þar til $a_ n$ og $b_ n$ eru búnir að berjast.

Tómas vinnur orrustuna ef hann vinnur fleiri einvígi heldur en óvinur sinn.

Tómas er nýbúinn að kaupa viðbótarpakka fyrir leikinn og í því var eitt Ofurseyði. Ofurseyðið virkar þannig að ef Tómas notar það þá mun styrkleikur hermanna hans verða sterkari um $k$ í næstu $m$ einvígum.

Tómas er ekki alveg viss um hvenær hann á að nota Ofurseyðið. Ef hann myndi velja besta tímann til að nota það, myndi Tómas geta unnið orrustuna?

Inntak

Fyrsta lína inniheldur tvær heiltölur $n,m,k$, þar sem $1 \le m \le n \le 10^5, 1 \le k \le 10^7$. Önnur lína inniheldur $n$ heiltölur $a_1, a_2, \dotsc , a_ n$, þar sem $1 \le a_ i \le 10^7$. Þriðja lína inniheldur $n$ heiltölur $b_1, b_2, \dotsc , b_ n$, þar sem $1 \le b_ i \le 10^7$.

Úttak

Ef Tómas getur unnið orrustuna skrifið þá út fyrsta tíman sem hann gæti notað Ofurseyðið og unnið orrustuna. Ef Tómas getur ekki unnið orrustuna skrifið þá út Neibb.

Stigagjöf

3 2 1
3 2 1
2 2 1

0

5 2 100
1 1 1 1 1
101 101 101 1 1

Neibb