plaja

Zizi îşi va petrece concediul în această vară într-o frumoasă staţiune de la Marea Neagră. Acolo va sta $N$ zile. Zilele sunt numerotate de la $1$ la $N$. În fiecare dintre cele $N$ zile de concediu, ea intenţionează să facă plajă un număr cât mai mare de unităţi de timp. Va trebui să ţină seama totuşi de prognoza meteo, care este nefavorabilă în $K$ dintre cele $N$ zile, respectiv în zilele $z_1$, $z_2$, $\dots$, $z_k$. În fiecare dintre aceste $K$ zile va ploua sau va fi prea mult soare, iar Zizi va trebui să-şi limiteze timpii de plajă la cel mult $t_1$, $t_2$, $\dots$, $t_k$ unităţi de timp. De asemenea, din motive de confort fizic, Zizi doreşte ca diferenţa în valoare absolută a timpilor de plajă între oricare două zile consecutive să nu depăşească $T$.

Cerință

Cunoscând zilele $z_1$, $z_2$, $\dots$, $z_k$ în care există limitările $t_1$, $t_2$, $\dots$, $t_k$ pentru timpul de plajă şi valoarea $T$, să se determine numărul maxim de unităţi de timp pe care Zizi le poate petrece la plajă într-o singură zi dintre cele $N$ zile de concediu.

Date de intrare

Fișierul plaja.in conține pe prima linie trei numere naturale $N$, $K$ şi $T$ separate printr-un spaţiu, reprezentând numărul de zile de concediu, numărul de zile în care există limitări pentru timpul de plajă şi diferenţa maximă admisă a timpilor de plajă pentru oricare două zile consecutive. Pe fiecare dintre următoarele $K$ linii se află câte două numere $z$ şi $t$, despărțite printr-un spațiu, reprezentând numărul de ordine al unei zile cu limitări pentru timpul de plajă, respectiv limita de timp pentru ziua respectivă. Valorile $z_1$, $z_2$, $\dots$, $z_k$ sunt în ordine strict crescătoare.

Date de ieșire

Fișierul plaja.out va conține pe prima linie un singur număr natural tmax, reprezentând numărul maxim de unităţi de timp pe care Zizi le poate petrece făcând plajă într-una din cele $N$ zile de concediu.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000 \ 000$
• $1 \leq K \leq 100 \ 000$
• $1 \leq t_1, t_2, \dots, t_k \leq 100 \ 000$
• $1 \leq z_1 < z_2 < \dots < z_k \leq N$
• $2 \leq T \leq 1 \ 000 \ 000$
• Pentru $20$% din punctajul total există teste cu $1 \leq N, K \leq 1 \ 000$
• Pentru $65$% din punctajul total există teste cu $1 \leq N, K \leq 100 \ 000$

Exemplul 1

plaja.in

3 1 3
1 2

plaja.out

8

Explicație

În ziua $1$ timpul de plajă este limitat la $2$ unități de timp. În ziua a doua timpul maxim de plajă este $2 + 3$, iar în ziua a treia, timpul maxim este $2 + 3 + 3 = 8$ unități de timp.

Exemplul 2

plaja.in

5 2 11
2 2
4 5

plaja.out

16

Explicație

În ziua $2$ timpul de plajă este limitat la $2$ unități de timp, iar în zilele $1$ și $3$ nu există limitare. Atunci timpul maxim de plajă pentru zilele $1$ sau $3$ este $2 + 11 = 13$. În ziua $4$ timpul de plajă este limitat la $5$ unități de timp, iar în ziua $5$ nu există limitare. Deci în ziua $5$ timpul maxim de plajă este $5 + 11 = 16$.