== include(page="template/taskheader" task_id="plaja2") ==

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~}, ..., z{~k~}.  În fiecare dintre aceste *K* zile va ploua sau va fi prea mult soare, iar Zizi va trebuisă-şi limiteze timpiide plajă la cel mult t{~1~}, t{~2~}, ..., 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*.

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~}, ..., z{~k~}.  În fiecare dintre aceste $K$ zile va ploua sau va fi prea mult soare, iar Zizi va trebuisă-şi limiteze timpiide plajă la cel mult t{~1~}, t{~2~}, ..., 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$.

h2. 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~}, ..., z{~k~} sunt în ordine strict crescătoare.

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~}, ..., z{~k~} sunt în ordine strict crescătoare.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ N ≤ 10^9^$

* $1 ≤ t{~1~} , t{~2~} ... t{~3~} ≤ 10^5^$
* $1 &le; z{~1~} < z{~2~} < ... < z{~k~}$
* $1 &le; T &le; 100000$
* $Pentru 20 % din punctajul total există teste cu 1 &le; N,K &le; 1000$

* $1 ≤ K ≤ 10^5^$
* $1 ≤ t{~1~} , t{~2~} ... t{~K~} ≤ 10^5^$
* $1 &le; z{~1~} < z{~2~} < ... < z{~k~} &le; N$
* $1 &le; T &le; 1000000$
* $Pentru 20% din punctajul total există teste cu 1 &le; N, K &le; 1000$
* $Pentru 65% din punctajul total exista teste cu 1 &le; N, K &le; 100000$

h2. Exemplu
table(example). |_. plaja2.in |_. plaja2.out |
| 3 1 3

  1 2

1 2

| 8 |
| 5 2 11

  2 24 5

2 2
4 5

| 16 |
h3. Explicaţie