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.