8684번 - Losy 다국어

W pewnej szkolnej zabawie przygotowano n 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ć g 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 g 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.

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

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

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 g godzin.