Checkin

checkin

== include(page="template/taskheader" task_id="checkin") ==

Ministerul organizează o excursie pentru olimpici la Paris. Suntem toţi la aeroport, K olimpici având în total P bagaje. Olimpicii la informatică trebuie să rezolve acum următoarea problemă.
Pentru zborul către Paris au fost deschise N ghişee pentru check-in, numerotate de la 1 la N. La fiecare ghişeu lucrează exact un angajat. Angajatul de la ghişeul i are nevoie de Ai secunde pentru a procesa fiecare bagaj al clientului prezentat la ghişeu şi Bi secunde pentru a emite toate tichetele de îmbarcare solicitate de client (acelaşi timp Bi, indiferent de numărul de tichete solicitate de client).
O persoană poate sta la un singur ghişeu şi poate preda 0, 1 sau mai multe bagaje (acestea vor fi trecute pe numele său). Evident, aceeaşi persoană nu poate sta la mai multe ghişee. De asemenea, o persoană poate să prezinte angajatului de la ghişeu biletele şi paşapoartele altor persoane, astfel că poate solicita emiterea mai multor tichete de îmbarcare. O persoană trebuie să solicite de la ghişeul la care se prezintă cel puţin un tichet de îmbarcare.
Iniţial nimeni nu stă la coadă la ghişeele pentru Paris. Timpul necesar pentru a face check-in-ul (predarea tuturor celor P bagaje şi obţinerea tichetelor de îmbarcare pentru toţi cei K olimpici) depinde de strategia adoptată (alegerea ghişeelor, stabilirea persoanelor care stau la coadă la ghişee şi împărţirea bagajelor). Olimpicii la informatică trebuie să găsească o strategie prin care cei K olimpici pot preda cele P bagaje şi obţine cele K tichete de îmbarcare în cel mai scurt timp.
 
h2. Cerinta
 
Scrieţi un program care să determine timpul minim necesar pentru check-in.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare checkin.in conţine pe prima linie numărul natural N reprezentând numărul de ghişee pentru check-in. Urmează N linii pe care sunt descrise ghişeele. Pe linia i+1 sunt scrise numerele naturale Ai Bi (separate prin spaţiu) reprezentând timpul necesar angajatului de la ghişeul i pentru a procesa un singur bagaj al clientului de la ghişeu, respectiv timpul necesar pentru emiterea tuturor tichetelor de îmbarcare solicitate de clientul de la ghişeu. Pe ultima linie sunt scrise numerele naturale K şi P, separate prin spaţiu, reprezentând numărul de olimpici şi numărul de bagaje pe care le au.

Fişierul de intrare $checkin.in$ ...

h2. Date de ieşire

Fişierul de ieşire checkin.out va conţine o singură linie pe care va fi scris timpul minim pentru check-in.

În fişierul de ieşire $checkin.out$ ...

h2. Restricţii

* 1 ≤ N ≤ 1000
* 1 ≤ Ai, Bi ≤ 1000
* 1 ≤ K ≤ 10000
* 0 ≤ P ≤ 10000

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. checkin.in |_. checkin.out |

| 6
10 100
20 80
20 40
40 50
20 10
10 10
4 10
| 70
|
 

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 

h3. Explicaţie

O persoană stă la ghişeul 3, predă un bagaj şi ia un tichet de îmbarcare.
O a doua persoană stă la ghişeul 5, predă 3 bagaje şi ia un tichet de îmbarcare.
O a treia persoană stă la ghişeul 6, predă 6 bagaje şi ia 2 tichete de îmbarcare.
A patra persoană nu stă la ghişeu.

...

== include(page="template/taskfooter" task_id="checkin") ==