problema/plaja2

plaja2

Toata lumea se fute pe plaja. Si pisicile e semafor; CAAAAAAAAAAAAAAMIOANIE.

== 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$.
 
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.
 
h2. Date de ieşire
 
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 ≤ 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
| 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") ==
 

public

task: plaja2