Un sir de
n persoane sunt asezate la un
ghiseu pentru a depune declaratii de venit ale unor firme, fiecare persoana
având de depus una sau mai multe declaratii.
Se stie ca depunerea unei declaratii dureaza exact un minut si în minutul
1 începe depunerea primei declaratii.
Pentru fiecare persoana se cunosc: numarul de declaratii pe care le are de depus
si minutul limita pâna la care persoana poate ramâne la coada (dupa
minutul respectiv, ea fiind nevoita sa plece pentru a-si rezolva alte probleme).
Se stie ca o persoana va parasi coada numai în conditiile în care
i-a expirat timpul si nu a ajuns la ghiseu sau a ajuns la ghiseu, dar timpul
ramas (înainte de a fi nevoita sa plece) nu îi este suficient pentru
a depune toate declaratiile sale (in acest caz pleaca fara a mai depune vreo
declaratie).
Reprezentantul fiscal care preia declaratiile are nevoie de o pauza de exact
p minute pe care si le poate
lua, pe toate, în orice moment, cu conditia ca persoanele ale caror declaratii
pot fi preluate sa ramâna acelasi ca si în cazul în care acesta
nu si-ar lua nici o pauza. Evident, reprezentantul fiscal nu isi poate lua pauza
in timp ce serveste un client (adica in timp ce persoana aflata la ghiseu depune
declaratiile). În cazul în care lucrul acesta nu este posibil, reprezentantul
fiscal îsi va lua pauza dupa ce termina de primit toate declaratiile pe
care le poate prelua.
Cerinta
Se cere
sa se determine cel mai devreme moment când reprezentantul fiscal poate
sa îsi ia pauza.
Date de
intrare
Fisierul de intrare fisc.in
contine pe prima linie numarul natural n,
reprezentand numarul de persoane aflate la coada. Pe urmatoarele n
linii se afla informatii despre cele n
persoane care stau la coada. Mai exact, pe linia i+1
se afla doua numere naturale separate prin spatiu D
L, unde D reprezinta numarul
de declaratii pe care le are de depus persoana i,
iar L timpul limita pentru persoana
i. Pe ultima linie se afla numarul
natural p, reprezentand numarul
de minute de pauza ale reprezentantului fiscal.
Date de
iesire
Fisierul de iesire fisc.out
va contine o singura linie pe care va fi scris un numar natural care reprezinta
minutul (minim posibil) in care reprezentantul fiscal isi poate lua pauza.
Restrictii si precizari
0 < n <= 1000
Toate valorile din problema
sunt numere naturale.
0 < D <= 100
0 < L <= 10000
0 < p < 100
Exemplu
fisc.in
fisc.out
Explicatie
8
2 5
1 9
3 6
1 10
4 2
4 10
5 19
4 15
3
7
prof. Rodica
Pintea
Liceul "Grigore
Moisil" Bucuresti
Contact:ro_dica@yahoo.com
