A11898 | Songs Compression

Ivan has $n$ songs on his phone. The size of the $i$ -th song is $a_i$ bytes. Ivan also has a flash drive which can hold at most $m$ bytes in total. Initially, his flash drive is empty.

Ivan wants to copy all $n$ songs to the flash drive. He can compress the songs. If he compresses the $i$ -th song, the size of the $i$ -th song reduces from $a_i$ to $b_i$ bytes ( $b_i < a_i$ ).

Ivan can compress any subset of the songs (possibly empty) and copy all the songs to his flash drive if the sum of their sizes is at most $m$ . He can compress any subset of the songs (not necessarily contiguous).

Ivan wants to find the minimum number of songs he needs to compress in such a way that all his songs fit on the drive (i.e. the sum of their sizes is less than or equal to $m$ ).

If it is impossible to copy all the songs (even if Ivan compresses all the songs), print "-1". Otherwise print the minimum number of songs Ivan needs to compress.

The first line of the input contains two integers $n$ and $m$ ( $1 \le n \le 10^5, 1 \le m \le 10^9$ ) — the number of the songs on Ivan's phone and the capacity of Ivan's flash drive.

The next $n$ lines contain two integers each: the $i$ -th line contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le 10^9$ , $a_i > b_i$ ) — the initial size of the $i$ -th song and the size of the $i$ -th song after compression.

If it is impossible to compress a subset of the songs in such a way that all songs fit on the flash drive, print "-1". Otherwise print the minimum number of the songs to compress.