== 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 z1, z2, ..., zk.  Î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 t1, t2, ..., tk 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 z1, z2, ..., zk 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 ≤ t1 , t2 ... t3 ≤ 10^5^$
* $1 &le; z1 < z2 < ... < zk$
* $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