Scufiţa Roşie vrea din nou să ajungă la bunicuţa şi pentru asta trebuie să traverseze pădurea fermecată. Pe harta pădurii fermecate, casa Scufiţei Roşii se află în punctul de coordonate (0, 0), iar casa bunicii în punctul de coordonate (x, y).
Scufiţa Roşie iese din casă la momentul de timp 0 şi se deplasează cu viteză constantă de 1 m/s.
În pădurea fermecată apar, la anumite momente de timp, ziduri peste care Scufiţa Roşie nu poate trece. Dacă totuşi în momentul în care zidul apare Scufiţa Roşie se află chiar în poziţia în care apare zidul, ea va reuşi să treacă dincolo de zid. Zidurile sunt drepte paralele cu axa Ox. Pentru fiecare zid i (i=1, 2, ..., n; unde n reprezintă numărul de ziduri) cunoaştem momentul de timp t_i la care zidul apare, precum şi poziţia sa p_i (mai exact, zidul va fi o dreaptă cu ecuaţia y=p_i).

Cerinţă

Să se determine timpul minim în care Scufiţa Roşie poate ajunge la casa bunicii (dacă este posibil).

Date de intrare

Fişierul de intrare basm.in conţine pe prima linie două numere naturale separate prin spaţiu reprezentând coordonatele x y ale casei bunicii. Pe cea de a doua linie se află numărul natural n, reprezentând numărul de ziduri. Pe următoarele n linii sunt descrise cele n ziduri, câte un zid pe o linie, sub forma a două numere întregi separate prin spaţiu p_i t_i.

Date de ieşire

Fişierul de ieşire basm.out va conţine o singură linie pe care va fi scrisă valoarea -1 (dacă Scufiţa Roşie nu poate ajunge la casa bunicii). În caz contrar, pe prima linie se va scrie un număr real cu cel puţin 6 zecimale, reprezentând timpul minim în care Scufiţa Roşie ajunge la casa bunicii.

Restricţii

• 1 <= x, y, t_i <= 10⁹
• 0 <= n <= 100 000
• 1 <= p_i < y
• Nu există două ziduri în aceeaşi poziţie.
• Rezultatul afişat va fi considerat corect dacă diferenţa absolută dintre rezultatul corect şi cel afişat este <0.0001.

Exemple

basm.in	basm.out	basm.in	basm.out
7 7 1 4 5	10.00000000	7 7 1 4 3	-1

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com