Simulation - Lot 2017 Baraj 4 Juniori | curiosity2

Aventura robotului Curiosity pe Marte continuă. Robotul se deplasează de-a lungul unei axe de coordonate Ox. Punctul de plecare în incursiune are coordonata $x = 0$, iar punctul unde este finalizat studiul are coordonata $X_f$. Robotul se deplasează cu viteză constantă și parcurge o unitate de drum într-o unitate de timp.

Cercetătorii au stabilit $N$ zone ce fac posibilă recepția datelor transmise de robot către satelit. Fiecare zonă este definită prin pereche $X_i$, $L_i$ ($X_i$ – coordonata de început a zonei $i$, $L_i$ – lungimea zonei). Zonele nu interferează (nu au puncte comune). Datele sunt transmise în pachete de dimensiune fixă, iar durata de transmisie a unui pachet este $D$.

Pe parcursul unei zone robotul poate transmite unul sau mai multe pachete de date. După ce a finalizat transmisia unui pachet, robotul poate continua transmisia unui alt pachet, dacă este posibil (nu este acceptată transmiterea unui pachet incomplet), sau poate întrerupe transmisia. După întrerupere, robotul poate relua transmisia după cel puțin de $T$ unității de timp consumate.

Cerinţă

Să se determine numărul maxim de pachete de date ce pot fi transmise de către robot satelitului.

Date de intrare

Fişierul curiosity2.in conţine pe prima linie patru numere naturale $X_f$, $D$, $T$, $N$ cu semnificația din enunț. Pe următoarele $N$ linii descrierea zonelor: $X_i$, $L_i$, numere naturale, unde $X_i$ reprezintă coordonata de început a zonei $i$, iar $L_i$ lungimea zonei.

Date de ieșire

Fişierul curiosity2.out conţine pe o singură linie un singur număr natural ce reprezintă numărul maxim de pachete de date ce pot fi transmise de către robot.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq D \leq 10^6$;
• $1 \leq T \leq 10^9$;
• $0 < L_i, X_f \leq 10^9$;
• $0 \leq X_i \leq X_f$;
• Transmisiile pot fi efectuate doar în zonele specificate;
• Transmisia unui pachet începe și se termină în coordonate întregi;
• Robotul poate începe transmisia unui pachet numai dacă anterioara transmisie s-a finalizat;
• Când atinge coordonata $X_f$ robotul trebuie să finalizeze transmisiile;
• Zonele sunt date în ordine crescătoare a distanței față de origine.

Exemplu

curiosity2.in

16 2 3 3
2 5
8 4
14 3

curiosity2.out

4

Explicație