check-in

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.

Cerinţă

Scrieţi un program care să determine timpul minim necesar pentru check-in.

Date de intrare

Fişierul de intrare check-in.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.

Date de ieşire

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

Restricţii şi precizări

• $1 \leq N \leq 1 \ 000$
• $1 \leq A_i, B_i \leq 1 \ 000$
• $1 \leq K \leq 10 \ 000$
• $0 \leq P \leq 10 \ 000$

Exemplu

check-in.in

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

check-in.out

70

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.