Losy

Limit pamięci: 32 MB

W pewnej szkolnej zabawie przygotowano koszyków i do każdego z nich wrzucono pewną liczbę losów. Niektóre z losów są wygrywające i za wylosowanie takiego losu dostaje się prawo do opuszczenia jednej godziny lekcyjnej bez usprawiedliwienia.

Kozik szybko obliczył, że chciałby opuścić godzin w danym roku szkolnym. Powinien więc kupić tyle losów, aby mieć pewność, że wśród wszystkich kupionych będzie co najmniej losów wygrywających. Kozik ma jednak ograniczone fundusze, dlatego chciałby zrobić to jak najmniejszym kosztem, czyli kupić jak najmniej losów. Zakładamy, że Kozik wie, ile jest w każdym pojemniku losów wygrywających, a ile przegrywających.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite , (), oznaczające odpowiednio liczbę koszyków z losami oraz liczbę godzin, jakie chciałby opuścić Kozik.

W kolejnych wierszach znajduje się opis kolejnych koszyków. Każdy wiersz zawiera dwie liczby całkowite (), oznaczające odpowiednio liczbę losów wygrywających oraz przegrywających w -tym koszyku.

W testach wartych około punktów zachodzi dodatkowy warunek .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnej liczbie losów, jakie powinien kupić Kozik lub jedno słowo NIE, gdy Kozik nie może kupić tylu losów, aby opuścić co najmniej godzin.

Przykład

Dla danych wejściowych:

4 3
2 5
0 5
2 0
2 2

poprawną odpowiedzią jest:

5

Autor zadania: Jacek Tomasiewicz.