복권

어느 학교 행사에서 바구니 $n$개를 준비하고, 각 바구니에 복권을 여러 장 넣었다. 복권 중 일부는 당첨 복권이며, 당첨 복권을 뽑으면 수업 한 시간을 사유 없이 빠질 수 있는 권리를 얻는다.

Kozik은 올해 총 $g$시간을 빠지고 싶어 한다. 따라서 당첨 복권을 최소 $g$장 확보해야 한다. 그런데 어떤 복권이 자기 손에 들어올지는 고를 수 없으므로, 어떤 복권이 나오더라도 산 복권 안에 당첨 복권이 반드시 $g$장 이상 포함되도록 확실하게 사야 한다. 돈이 넉넉하지 않아, 사는 복권 수를 최소로 하고 싶다.

Kozik은 각 바구니에 당첨 복권과 꽝 복권이 각각 몇 장인지 정확히 안다. 한 바구니에서 복권을 뽑을 때는 최악의 경우를 가정한다. 즉, 그 바구니의 꽝 복권이 모두 먼저 나온 뒤에야 당첨 복권이 나온다. 따라서 당첨 복권 $w$장과 꽝 복권 $p$장이 든 바구니에서 당첨 복권 $k$장($k \le w$)을 확실히 얻으려면 그 바구니에서 $p + k$장을 사야 한다.

당첨 복권을 최소 $g$장 확실히 확보하기 위해 Kozik이 사야 하는 복권 수의 최솟값을 구하여라.

첫 줄에 두 정수 $n$, $g$($1 \le n \le 10000$, $1 \le g \le 1000$)가 주어진다. 각각 바구니의 수와 Kozik이 빠지고 싶은 시간 수를 뜻한다.

다음 $n$개의 줄에 각 바구니의 정보가 주어진다. $i$번째 줄에는 두 정수 $w_i$, $p_i$($0 \le w_i \le 10^9$, $0 \le p_i \le 10^9$)가 있으며, 각각 $i$번째 바구니의 당첨 복권 수와 꽝 복권 수를 뜻한다.

당첨 복권을 최소 $g$장 확실히 확보하기 위해 사야 하는 복권 수의 최솟값을 정수 하나로 출력한다. 만약 불가능하다면(모든 바구니의 당첨 복권을 합쳐도 $g$장이 되지 않으면) 대신 NIE를 출력한다.