fisc

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
  

Timp maxim de executie/test: 0.1 secunde

prof. Rodica Pintea
Liceul "Grigore Moisil" Bucuresti
Contact:ro_dica@yahoo.com