Mladi DP je napokon dobio svoju prvu neplaćenu praksu. Njegov prvi zadatak je održavati planinsku komunikacijsku mrežu.
Planina je prekrivena snijegom, vjetar je snažan, a vidljivost loša ali DP mora osigurati da signal dopire od prvog do zadnjeg tornja.

Na planini se nalazi \(n\) tornjeva, poredanih redom. Visina \(i\)-tog tornja iznosi \(h_i\), a horizontalna pozicija mu je \(x_i\). DP smije povezivati tornjeve signalnim vezama. Cijena spajanja dvaju tornjeva s koordinatama \(x_i\) i \(x_j\) iznosi: \((x_i - x_j)^2\)

Signal ima ograničenu energiju. Ukupna suma cijena svih korištenih veza ne smije prelaziti \(maxEnergy\). Dodatno, zbog tehničkih ograničenja, nijedna pojedinačna veza ne smije imati cijenu veću od \(maxJump\). Ali snijeg stvara problem. Ako visina snijega naraste na \(S\), svi tornjevi s visinom manjom ili jednakom \(S\) postaju zatrpani i više ih nije moguće koristiti niti spajati.

Vaš zadatak je odrediti najveću moguću visinu snijega \(S\) takvu da je i dalje moguće ostvariti vezu (putem nekog niza veza) između prvog i zadnjeg tornja, poštujući ograničenja \(maxEnergy\) i \(maxJump\). Ako nije moguće spojiti prvi i zadnji toranj ni za \(S = 0\), ispišite \(-1\).

Ulazni podaci

U prvom retku nalaze se tri prirodna broja: \(n\), \(maxEnergy\), \(maxJump\) (\(1 \leq n \leq 2\cdot 10^5\), \(1 \leq maxEnergy \leq 10^{18}\), \(1 \leq maxJump \leq 10^{18}\))

U idućih \(n\) redova nalaze se parovi prirodnih brojeva: \(x_i\) \(h_i\) (\(1 \leq x_i, h_i \leq 10^{18}\)), gdje je \(x_i\) horizontalna koordinata tornja, a \(h_i\) njegova visina.

Izlazni podaci

Ispišite jedan broj — najveću moguću visinu snijega \(S\) takvu da je moguće ostvariti vezu između prvog i zadnjeg tornja.

Ako to nije moguće ni za \(S = 0\), ispišite \(-1\).

Podzadatci

Ulaz primjera 1

4 10 9
1 1
2 2
3 3
10 10

Izlaz primjera 1

-1

Ulaz primjera 2

3 1 1
1 1
5 5
10 10

Izlaz primjera 2

-1

Ulaz primjera 3

5 1000000000000000000 1000000000000000000
5 5
7 7
9 9
11 11
13 13

Izlaz primjera 3

4