codeforces 1015C

C. Songs Compression

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Ivan has nn songs on his phone. The size of the ii-th song is aiai bytes. Ivan also has a flash drive which can hold at most mm bytes in total. Initially, his flash drive is empty.

Ivan wants to copy all nn songs to the flash drive. He can compress the songs. If he compresses the ii-th song, the size of the ii-th song reduces from aiai to bibi bytes (bi<aibi<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 mm. 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 mm).

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 nn and mm (1≤n≤105,1≤m≤1091≤n≤105,1≤m≤109) — the number of the songs on Ivan's phone and the capacity of Ivan's flash drive.

The next nn lines contain two integers each: the ii-th line contains two integers aiai and bibi (1≤ai,bi≤1091≤ai,bi≤109, ai>biai>bi) — the initial size of the ii-th song and the size of the ii-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

output

Copy

input

Copy

output

Copy

-1

题意：给你n件物品，和一个空间为m的背包，这n件物品的初始占用空间为ai，其占用空间可以缩小为bi，但是需要花费ai-bi的花费，求在花费最小的情况下有多少物品不用被压缩
题解：我们换个方向，这n个物品被压缩后的大小为bi，先全部加起来，如果压缩后的物品空间大小小于空间m，那么就可以把所有的物品加入背包，为了使花费最小，
　　　我们剩下的空间必须尽量装满，所以我们就将花费按照从小到大排序，一个个装，装到不能装了后就跳出来就行

代码如下：

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define fuck(x) cout<<"["<<x<<"]";

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int maxn = 1e5+;

LL a[maxn];

LL b[maxn];

LL c[maxn];

int main(){

#ifndef ONLINE_JUDGE

    FIN

#endif

    LL n,m;

    LL sumb=;

    int flag=;

    scanf("%lld%lld",&n,&m);

    for(int i=;i<n;i++){

        scanf("%lld%lld",&a[i],&b[i]);

        c[i]=a[i]-b[i];

        sumb+=b[i];

    }

    if(sumb>m){

        cout<<"-1"<<endl;

    }else{

        sort(c, c + n);

        int ans = ;

        for (int i = ; i < n; i++) {

            if (sumb + c[i] <= m) {

                sumb += c[i];

                ans++;

            }

            else break;

        }

        printf("%lld\n", n - ans);

    }

}

巴特西

codeforces 1015C

最新文章

热门文章