| Fişierul intrare/ieşire: | plaja2.in, plaja2.out | Sursă | ONI 2018, clasa a 9-a, ziua 1 |
| Autor | Constantin Galatan | Adăugată de |  Serban Cercelescu •oldatlantian |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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.
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.
Restricţii
- 1 ≤ N ≤ 109
- 1 ≤ K ≤ 105
- 1 ≤ t1 , t2 ... tK ≤ 105
- 1 ≤ z1 < z2 < ... < zk ≤ N
- 1 ≤ T ≤ 1000000
- Pentru 20% din punctajul total există teste cu 1 ≤ N, K ≤ 1000
- Pentru 65% din punctajul total exista teste cu 1 ≤ N, K ≤ 100000
Exemplu
| plaja2.in | plaja2.out |
|---|---|
| 3 1 3 1 2 | 8 |
| 5 2 11 2 2 4 5 | 16 |
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.
