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?
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$.
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.
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 |