3. Lietajúce Taniere

Pozemšťanské Národné Múzeum v Sekulách vystavuje skutočný skvost: Najvzácnejšiu hlásku galaxie¹. Táto hláska je lokálny endemit – nevyskytuje sa vo fonológií jazyka žiadnej inej planéty, a preto má obrovskú hodnotu. A práve preto bola v piatok cez obedovú prestávku ukradnutá rafinovaným páchateľom. Nie je ním nik iný, ako interstelárny kriminálnik Okáň Hruškový, prezývaný “Bzučiak”. Samotná krádež bola pre neho hračkou, skutočná skúška jeho schopností nastáva až teraz: s ukradnutou hláskou sa musí dostať na najbližšiu matriku, kde si zmení meno na Okäň, čím zmätie agentov zákona, zahladí všetky stopy po svojej kriminálnej histórií a šťastný odíde do dôchodku. Samozrejme, poletí lietajúcim tanierom².

Má to však háčik: Medzi Pozemšťanským Národným Múzeom v Sekulách a Sekulským Matričným Úradom nejde žiaden priamy let, preto musí Bzučiak prestúpiť na Hlavnej Tanierovej Stanici Sagittarius A.

Okrem toho je problémom, že galaktická polícia má agentov zákona všade. Normálne síce pre Bzučiaka žiaden problém nepredstavujú³, pokiaľ ale poletí rovnakým letom ako jeden z nich, môže sa s novým menom rozlúčiť.

Ako nový zamestnanec IT oddelenia galaktickej polície ste dostali časy odletov všetkých liniek, spolu s pridelenými financiami, za ktoré môžete nakúpiť niekoľkým policajtom letenky, aby ste Bzučiakovi znemožnili využitie týchto letov. Vašou úlohou je Bzučiakovi cestu čo najviac znepríjemniť, pokiaľ možno úplne znemožniť.

Úloha

Máte dané časy odchodov všetkých \(n\) letov z Národného Múzea do Tanierovej Stanice, ako aj ich dĺžku \(d_a\), ktorá je, samozrejme, pre všetky rovnaká. Rovnako máte dané aj odchody všetkých \(n\) letov z Tanierovej Stanice na Matričný Úrad, a ich dĺžku \(d_b\). Máte peniaze na zablokovanie \(k\) letov – určte, v akom najneskoršom čase môžeme Bzučiaka prinútiť dostať sa na Matričný Úrad, respektíve či vieme Bzučiakovi v jeho dosiahnutí úplne zabrániť.

Bzučiak môže prestúpiť medzi dvoma letmi, pokiaľ čas príchodu prvého nie je vyšší ako čas odchodu druhého, pričom dĺžka letu je definovaná ako rozdiel v časoch jeho príchodu a odchodu.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú 4 celé čísla \(n, d_a, d_b, k\) - počet letov na každej linke, dĺžky letov prvej a druhej linky, a počet lístkov, ktorý si môžeme dovoliť kúpiť, pričom vždy platí \(1 \leq d_a,d_b\) a \(1 \leq k \leq 2n\).

Nasledujú dva riadky. Na prvom z nich je \(n\) rôznych celých čísel \(a_0\) až \(a_{n-1}\), ktoré označujú časy odchodov letov prvej linky. Na druhom z nich je \(n\) rôznych celých čísel \(b_0\) až \(b_{n-1}\), ktoré označujú časy odchodov letov druhej linky. Platí, že oba riadky sú zoradené vo vzostupnom poradí, a okrem toho všetky časy odletov \(x\) spadajú do nasledovného rozmedzia: \(1 \leq x \leq 10^{9}\).

Formát výstupu

Na jediný riadok výstupu vypíšte jediné číslo – najneskorší čas, v akom môžeme Bzučiaka donútiť doraziť do cieľovej zastávky. Pokiaľ je možné Bzučiakovi zabrániť v dosiahnutí cieľa úplne, vypíšte číslo \(-1\). Nezabudnite na konci vypísať symbol konca riadku.

Hodnotenie

Sú 4 sady vstupov:

• V prvej sade platí, že \(1 \leq n \leq 100\), \(d_a = d_b = 1\) a obe linky majú rovnaké časy odletov, teda \(a_i = b_i\) pre všetky \(0 \leq i \leq n-1\).
• V druhej sade platí, že \(1 \leq n \leq 10\,000\).
• V tretej sade platí, že \(1 \leq n \leq 100\,000\).
• V štvrtej sade platí, že \(1 \leq n \leq 1\,000\,000\).

Príklad

Input:

4 3 5 3
1 2 3 6
6 7 8 9

Output:

14

Zablokujeme napríklad prvé tri lety z Národného Múzea. Bzučiak nebude mať inú možnosť, ako využiť ten posledný, s odchodom v čase 6. V Tanierovej Stanici bude v čase 9, stihne rýchlo nastúpiť na posledný let na Matričný Úrad, ktorý k nemu dorazí v čase 14. Alternatívne sme mohli zablokovať prvé tri lety druhej linky a dosiahnuť rovnaký výsledok.

Input:

6 2 1 4
1 3 5 7 9 11
3 4 5 6 10 13

Output:

-1

V tomto prípade vieme Bzučiaka od Matričného Úradu úplne odrezať, napríklad zablokovaním prvých dvoch letov z Národného Múzea a posledných dvoch letov z Tanierovej Stanice. Bzučiak odletí najskorším letom s odchodom v čase 5, v Tanierovej Stanici bude v čase 7, a nestíha už žiaden nezablokovaný let ďalej.