Fişierul intrare/ieşire:plaja2.in, plaja2.outSursăONI 2018, clasa a 9-a, ziua 1
AutorConstantin GalatanAdăugată deoldatlantianSerban Cercelescu oldatlantian
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inplaja2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?