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

Poveste şi cerinţă...

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 de intrare $plaja2.in$ ...

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

În fişierul de ieşire $plaja2.out$ ...

Fişierul plaja.outva 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 Nzile de concediu.

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

* $1 ≤ t ~1~ , t ~2~ ... t ~k~ ≤ 10^5^$
* $1 &le; z ~1~ < z ~2~  < ... < z ~k~ $

* $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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 3 1 3
1 2
| 8 |
| 5 2 11
2 2
4 5
| 16 |

h3. Explicaţie

...

Pentru primul exemplu:
Î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.
 
Pentru al doilea exemplu:
Î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 3este 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.

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