== include(page="template/taskheader" task_id="checkin") ==
Poveste şi cerinţă...
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 $A{~i~}$ secunde pentru a procesa fiecare bagaj al clientului prezentat la ghişeu şi $B{~i~}$ secunde pentru a emite toate tichetele de îmbarcare solicitate de client (acelaşi timp $B{~i~}$, 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.
h2. Date de intrare
Fişierul de intrare $checkin.in$ ...
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 $A{~i~}$ $B{~i~}$ (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.
h2. Date de ieşire
În fişierul de ieşire $checkin.out$ ...
Fişierul de ieşire $checkin.out$ va conţine o singură linie pe care va fi scris timpul minim pentru check-in.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000$
* $1 ≤ A{~i~}, B{~i~} ≤ 1.000$
* $1 ≤ K ≤ 10.000$
* $0 ≤ P ≤ 10.000$
h2. Exemplu
table(example). |_. checkin.in |_. checkin.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
10 100
20 80
20 40
40 50
20 10
10 10
4 10
| 70
|
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") ==
