시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 0 0 0.000%

문제

Firma BajtoLicz posiada bardzo szybki serwer - BL87. W celu wykorzystania jego możliwości, firma 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 firmę 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.

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.

입력

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 ≤ ab ≤ 1 000 000 000), reprezentujące odpowiednio, czas pojawienia się programu oraz czas procesora potrzebny na jego wykonanie.

출력

Twój program, w pierwszym i jedynym wierszu wyjścia, powinien wypisać jedną liczbę całkowitą k - minimalny sumaryczny czas wykonania wszystkich programów.

예제 입력 1

3
0 6
20 8
15 10

예제 출력 1

29