AlgoLiga 2018

Bitazar właśnie otworzył własną pizzerię. Pomysł ten okazał się strzałem w dziesiątkę i już pierwszego dnia dostał mnóstwo zamówień. Boi się nawet, że nie zdąży wszystkich zrealizować na czas. Szczęśliwie ma do dyspozycji skuter oraz wszystkie miejsca dostaw znajdują się na najdłuższej ulicy w jego miejscowości - ulicy Bitonicznej. Bitazar pracę zaczyna bardzo wcześnie i nie chce zawieść swoich klientów. Aby tego dokonać, i-te zamówienie musi zostać zrealizowane przed upływem czasu t_i minut od początku pracy Bitazara. Przejechanie jednego kilometra zajmuje mu jedną minutę, a czas wręczenia zamówienia jest zaniedbywanie mały. Bitazar może zacząć pracę w dowolnym miejscu na ulicy Bitonicznej. Pomóż mu ustalić ile minimalnie minut potrzebuje na zrealizowanie wszystkich zamówień.

Wejście

W pierwszym wierszu wejścia znajduje się liczba naturalna 1<=n<=5000 oznaczająca liczbę zamówień. W każdym z następnych n wierszy znajdują się dwie liczby całkowite, kolejno: 0<=d<=10⁶ oraz 0<=t<=10⁹ będące odpowiednio odległością miejsca dostawy w kilometrach od północnego końca ulicy Bitonicznej oraz czasem w minutach od początku pracy Bitazara, przed którego upływem dane zamówienie należy dostarczyć. Na wejściu nie będzie dwóch wierszy z tą samą liczbą d.

Wyjście

Na wyjście należy wypisać minimalną liczbę minut, które Bitazar musi poświęcić na zrealizowanie wszystkich dostaw lub słowo "NIE", jeśli nie jest możliwe zrealizowanie wszystkich dostaw na czas.

Przykład

Wejście:
5
1 3
3 1
5 6
8 19
10 15

Wyjście:
11

Wyjaśnienie do przykładu:

Bitazar może rozpocząć podróż przy miejscu o parametrach (3,1), a następnie dostarczać zamówienia kolejno: (1,3), (5,6), (8,19) i (10,15). W ten sposób jego czasy dostawy w minutach w kolejnych miejscach to: 0, 2, 6, 9, 11. Ponadto 11 minut to najszybciej jak się da zrealizować wszystkie zamówienia w tym przypadku.