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 Xf. 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ța

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

Date de intrare

Fișierul de intrare curiosity2.in conţine pe prima linie patru numere naturale Xf, 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 de ieșire curiosity2.out va 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 ≤ N ≤ 100000
• 1 ≤ D ≤ 106
• 1 ≤ T ≤ 109
• 0 < Li, Xf ≤ 109
• 0 ≤ Xi ≤ Xf
• 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 Xf 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