Rezolvare PBinfo #2455

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 trebui să-şi limiteze timpii de 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.

Cerința

Cunoscând zilele z[1], z[2], …, z[k] în care există limitările t[1], t[2], …, 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 de intrare plaja2.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.

Date de ieșire

Fișierul de ieșire plaja2.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 ≤ N ≤ 1 000 000 000
• 1 ≤ K ≤ 100 000
• 1 ≤ t[1], t[2], ..., t[k] ≤ 100 000
• 1 ≤ z[1] < z[2] < ... < z[k] ≤ N
• 2 ≤ T ≤ 1 000 000
• Pentru 20% din punctajul total există teste cu 1 ≤ N, K ≤ 1 000
• Pentru 65% din punctajul total există teste cu 1 ≤ N, K ≤ 100 000

Exemplul 1:

plaja2.in

3 1 3
1 2

plaja2.out

8

Explicație

În prima zi 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:

plaja2.in

5 2 11
2 2
4 5

plaja2.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.