Problem description

Łukasz znany jest ze swojej niezwykłej techniki czytania treści zadań. Na początku konkursu dzieli je na N kupek, na i-tej z nich znajduje się x_i treści, a przeczytanie każdej z nich zajmuje mu t_i sekund.

Niezwykłość techniki Łukasza polega na tym, że kolejno wybiera dwie nieprzeczytane jeszcze treści, z dwóch różnych kupek i oraz j, a następnie czyta je na raz, co zajmuje mu max (t_i,t_j) sekund, po czym wyrzuca je pod stół. Oczywiście Łukasz może także przeczytać tylko jedną treść z kupki i, co zajmuje mu t_i sekund.

Twoim zadaniem jest obliczenie ile minimalnie czasu potrzebuje Łukasz na przeczytanie wszystkich treści.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, będąca liczbą kupek. W i-tym z kolejnych N wierszy znajdują się dwie liczby całkowite x_i oraz t_i, będące odpowiednio liczbą treści znajdujących się na i-tej kupce oraz czasem potrzebnym na przeczytanie jednej z nich.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca minimalnym czasem potrzebnym Łukaszowi na przeczytanie wszystkich treści.

Ograniczenia

1 ≤ N ≤ 1 000, 1 ≤ x_i ≤ 10 000, 1 ≤ t_i ≤ 10⁹.

Przykład

3
3 8
2 2
2 5

26

3
1 20
5 9
3 3

56

3
2 8
2 6
2 7

23