Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_10_09 - Dostawca pizzy

pizzaBitazar 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 ti 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<=106 oraz 0<=t<=109 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.


Dodane przez:Adam Bąk
Data dodania:2013-09-11
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.