Superkomputer
Runda próbna, plik ¹ródªowy sup.*, dost¦pna pami¦¢ 16 MB
18 marca 2005
Firma BajtoLicz posiada bardzo szybki serwer - BL87. W celu wykorzystania jego mo»li-wo±ci, rma postanowiªa uruchomi¢ usªug¦ polegaj¡c¡ na wykonywaniu na serwerze programów przysyªanych przez klientów. Ka»dy przysªany program potrzebuje pewnej mocy obliczeniowej na swoje wykonanie. Czas wykonania programu liczy si¦ od momentu otrzymania przez rm¦
BajtoLicz programu, do chwili zako«czenia jego wykonywania. Serwer BL87 jest w stanie wykonywa¢ dowoln¡ liczb¦ programów równolegle ka»dy z wykonywanych programów otrzymuje pewien (zale»ny od przypisanego priorytetu) procent mocy procesora. Mo»liwe jest przerywanie i wznawianie wykonywania programów z ró»nymi priorytetami.
Firma zwróciªa si¦ do Ciebie z pro±b¡ o pomoc w napisaniu programu, który dla danej listy zlece« wyznaczy minimalny sumaryczny czas ich wykonania.
Zadanie
Napisz program, który:
• wczyta liczb¦ oraz opis programów, które musz¡ zosta¢ wykonane na serwerze,
• wyznaczy najkrótszy sumaryczny czas wykonania wszystkich zada«,
• wypisze wynik.
Wej±cie
Pierwszy wiersz zawiera liczb¦ caªkowit¡ n (1 ≤ n ≤ 100 000), oznaczaj¡ca liczb¦ programów do wykonania. Ka»dy z kolejnych n wierszy zawiera dwie liczby caªkowite a i b (0 ≤ a, b ≤ 1 000 000 000), reprezentuj¡ce odpowiednio, czas pojawienia si¦ programu oraz czas procesora potrzebny na jego wykonanie.
Wyj±cie
Twój program, w pierwszym i jedynym wierszu wyj±cia, powinien wypisa¢ jedn¡ liczb¦ caªkowit¡ k
minimalny sumaryczny czas wykonania wszystkich programów.
Przykªad
Dla danych wej±ciowych:
poprawnym wynikiem jest:
3
29
0 6
20 8
15 10