Raffle Tickets

At a school event there are $n$ baskets, and each basket is filled with a number of raffle tickets. Some tickets are winning: drawing a winning ticket earns the right to skip one class hour without an excuse.

Kozik has decided that he wants to skip $g$ hours this school year, so he needs to end up holding at least $g$ winning tickets. He will buy tickets from the baskets, but he cannot choose which individual tickets he receives, so he wants to be certain: no matter which tickets happen to come out, the tickets he buys must include at least $g$ winning ones. Because money is tight, he wants to buy as few tickets as possible.

Kozik knows exactly how many winning and how many losing tickets each basket holds. When he takes tickets from a basket, assume the worst case: every losing ticket in that basket comes out before any winning one. So to be guaranteed $k$ winning tickets from a basket that holds $w$ winning and $p$ losing tickets (with $k \le w$), he must take $p + k$ tickets from it.

Find the smallest total number of tickets Kozik must buy so that he is guaranteed at least $g$ winning tickets.

The first line contains two integers $n$ and $g$ ($1 \le n \le 10000$, $1 \le g \le 1000$): the number of baskets and the number of hours Kozik wants to skip.

Each of the next $n$ lines describes one basket with two integers $w_i$ and $p_i$ ($0 \le w_i \le 10^9$, $0 \le p_i \le 10^9$): the number of winning and losing tickets in the $i$-th basket.

Print a single integer: the minimum number of tickets Kozik must buy to be guaranteed at least $g$ winning tickets. If this is impossible (the baskets together hold fewer than $g$ winning tickets), print the word NIE instead.