Nén bài hát

Ivan có $n$ bài hát trong điện thoại. Bài hát thứ $i$ có kích thước $a_i$ byte. Ivan còn có một chiếc USB chứa được tối đa $m$ byte.

Ivan muốn chép toàn bộ $n$ bài hát vào USB. Anh có thể nén một số bài hát: nếu nén bài hát thứ $i$ thì kích thước của nó giảm từ $a_i$ xuống $b_i$ byte (với $b_i<a_i$).

Ivan có thể nén một tập con bất kỳ các bài hát (không nhất thiết liên tiếp, có thể là tập rỗng), rồi chép tất cả các bài hát vào USB nếu tổng kích thước của chúng không vượt quá $m$.

Hãy tìm số lượng bài hát ít nhất cần nén để tất cả các bài hát vừa với USB (tổng kích thước không vượt quá $m$). Nếu ngay cả khi nén tất cả các bài hát mà vẫn không vừa, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số bài hát và dung lượng của USB.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$: kích thước ban đầu và kích thước sau khi nén của bài hát thứ $i$.

Dữ liệu ra

In ra một số nguyên: số bài hát ít nhất cần nén để tất cả vừa với USB, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le {10}^9$
• $1\le b_i<a_i\le {10}^9$

Ví dụ