Start

2019-03-23 10:00 UTC

Alfa 2019

End

2019-03-23 16:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -239 days 6:19:54

Time elapsed

6:00:00

Time remaining

0:00:00

Problem L
Einvígi

/problems/iceland.einvigi/file/statement/is/img-0001.jpg
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

Hópur

Stig

Takmarkanir

1

50

$1 \le m \le n \le 1\, 000$, $1 \le k, a_ i \le 100$

2

100

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
3 2 1
3 2 1
2 2 1
0
Sample Input 2 Sample Output 2
5 2 100
1 1 1 1 1
101 101 101 1 1
Neibb