curiosity

Misiunea robotului Curiosity este de-a trimite imagini și informații către satelitul plasat pe orbita planetei Marte. Zona de explorare a robotului este de-a lungul unei axe de coordonate Ox. Robotul este înzestrat cu o baterie solară de capacitate energetică maximă $C$ și consumă pentru fiecare unitate de drum parcurs o unitate de energie. Coordonata punctului de plecare al incursiunii robotului (raportată la origine $x$ = $0$) este $X_s$, iar punctul unde este finalizat studiul are coordonata $X_f$.

Totodată, cercetătorii au stabilit $N$ puncte ce fac posibilă încărcarea bateriilor robotului, numerotate de la $1$ la $N$. În funcție de intensitatea luminii solare primite, reflectată în durata de încărcare a bateriei, punctele de încărcare sunt de trei tipuri: tipul $1$ – intensitate minimă/timp de încărcare mare, tipul $2$ – intensitate medie/timp de încărcare mediu, tipul $3$ – intensitate maximă/timp de încărcare scurt. Altfel, fiecare punct de încărcare $i$ este descris prin perechea $t_i$, $x_i$, adică tipul de încărcare, respectiv poziția acestuia pe axă. În orice punct de încărcare robotul poate decide dacă încarcă sau nu bateria, cu unități de energie, nu mai mult decât capacitatea maximă. Robotul se poate deplasa dintr-un punct atât în stânga cât și în dreapta pe axă.

Pentru a scurta durata parcurgerii distanței către punctul final se dorește determinarea unei strategi optime a opririlor pentru încărcarea bateriilor, astfel încât cantitatea totală de energie încărcată în puncte de tipul $1$ să fie minimă. În cazul în care sunt mai multe strategii de oprire pentru care cantitatea totală de energie încărcată în puncte de tipul $1$ este minimă, atunci se va alege strategia pentru care cantitatea totală de energie încărcată în puncte de tipul $2$ să fie minimă.

Cerinţă

Dacă se cunosc $X_s$, $X_f$, $C$, precum și descrierea celor $N$ puncte de încărcare să se determine o strategie de deplasare între coordonatele $X_s$ și $X_f$, optimă din punct de vedere al timpului necesar încărcării bateriilor.

Date de intrare

Fişierul curiosity.in conţine pe prima linie patru numere naturale $X_s$, $X_f$, $C$, $N$ cu semnificația din enunț. Pe următoarele $N$ linii este descrierea punctelor de oprire: $t_i$, $x_i$, unde $t_i$ reprezintă tipul de încărcare al punctului $i$, iar $x_i$ poziția acestuia pe axă.

Date de ieșire

Fişierul curiosity.out conţine pe o singură linie două numere naturale despărțite printr-un spațiu, ce reprezintă cantitatea totală minimă de energie încărcată în puncte de tipul $1$, respectiv cantitatea totală minimă de energie încărcată în puncte de tipul $2$. Dacă nu există soluție se va afișa valoarea $-1$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq C \leq 1 \ 000$
• $1 \leq t_i \leq 3$;
• $-10^6 \leq x_i \leq 10^6$
• $-10^6 \leq X_s < X_f \leq 10^6$. Acestea pot coincide cu coordonatele punctelor de încărcare;
• Punctele de încărcare sunt distincte. Coordonatele punctelor sunt de tip întreg;
• Punctele de încărcare sunt date în ordine crescătoare
• Atenție, în momentul plecării din punctul Xs robotul este încărcat la capacitatea maximă $C$.

Exemplu

curiosity.in

1 11 5 4
3 -1
1 3
2 7
3 10

curiosity.out

1 3

Explicație

Pe axa există $n = 4$ puncte de încărcare. Robotul pleaca din punctul $x_s$ = $1$ și trebuie să ajungă în punctul $x_f$ = $11$. Inițial robotul are bateria încărcată la capacitatea maximă $C = 5$ unități. Robotul oprește în punctul $x$ = $3$. Pentru deplasarea din $x$ = $1$ în $x$ = $3$ a consumat $2$ unități de energie. Încarcă bateria cu $1$ unitate (tip $1$). Bateria are în acest moment capacitatea de $4$ unități, suficiente pentru a ajunge în punctul $x$ = $7$ unde încarcă bateria cu $3$ unități (tip $2$). În punctul $x$ = $10$ încarcă bateria cu $1$ unitate (tip $3$).