C. Songs Compression

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Ivan has n

songs on his phone. The size of the i-th song is ai 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 ai to bi bytes (bi<ai

).

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.

Input

The first line of the input contains two integers n

and m (1≤n≤105,1≤m≤109

) — 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 ai and bi (1≤ai,bi≤109, ai>bi) — the initial size of the i-th song and the size of the i

-th song after compression.

Output

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.

Examples

Input

Copy

4 21
10 8
7 4
3 1
5 4

Output

Copy

2

Input

Copy

4 16
10 8
7 4
3 1
5 4

Output

Copy

-1

Note

In the first example Ivan can compress the first and the third songs so after these moves the sum of sizes will be equal to 8+7+1+5=21≤21

. Also Ivan can compress the first and the second songs, then the sum of sizes will be equal 8+4+3+5=20≤21. Note that compressing any single song is not sufficient to copy all the songs on the flash drive (for example, after compressing the second song the sum of sizes will be equal to 10+4+3+5=22>21

).

In the second example even if Ivan compresses all the songs the sum of sizes will be equal 8+4+1+4=17>16

.

大概题意：

就是输入n和m

m为存储空间

然后n行a和b   a大于b

每一行的a可以压缩为b的大小

求最少只需要压缩几个，使得m可以存下所有数据

如果全部压缩都不满足，就输出-1

 

思路：

定义个结构体，存下a，b和压缩节约的大小，即为a和b的差值c

算出最大的和sum2，和最小的和sum1

如果sum1也大于m，就输出-1

再用sort根据差值c从大到小排序

让sum2依次根据c从大到小减

直到sum2小于等于m即可

输出减去的个数即为压缩的次数

 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct no{
    ll a,b,c;
}x[100009];
bool cmp(no x1,no x2)
{
    return x1.c>x2.c;
}
int main()
{
    int n,i;
    ll m;
    while(scanf("%d%lld",&n,&m)!=EOF)
    {
        ll  sum1=0,sum2=0;
        ll t=0;
        for(i=1;i<=n;i++)
        {
            cin>>x[i].a>>x[i].b;
            sum1+=x[i].b;
            sum2+=x[i].a;
            x[i].c=x[i].a-x[i].b;
        }
        sort(x+1,x+1+n,cmp);
        if(sum1>m)cout<<"-1"<<endl;
        else if(sum2<=m)cout<<"0"<<endl;
        else
        {
            for(i=1;i<=n;i++)
            {
                sum2-=x[i].c;
                ++t;
                if(sum2<=m)
                    break;
            }
            cout<<t<<endl;
        }
    }
    return 0;
}