Codeforces Solution-C. Songs Compression-Solution in C, C++, Java, Python

Algorithm

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.

Input

The first line of the input contains two integers $n$ and $m$ ( $1 \leq n \leq 10^{5}, 1 \leq m \leq 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 \leq a_{i}, b_{i} \leq 10^{9}$ , $a_{i} > b_{i}$ ) — 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 \leq 21$ . Also Ivan can compress the first and the second songs, then the sum of sizes will be equal $8 + 4 + 3 + 5 = 20 \leq 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$ .

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 1;
int n, m;
long long t;
pair<int, int> a[N];

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.first - a.second) > (b.first - b.second);
}

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < n; ++i) {
    scanf("%d %d", &a[i].first, &a[i].second);
    t += a[i].first;
  }

  long long need = t - m;

  if(need <= 0) {
    puts("0");
    return 0;
  }

  sort(a, a + n, cmp);

  int res = 0;
  for(int i = 0; i < n; ++i) {
    if(need <= 0)
      break;
    ++res;
    need -= a[i].first - a[i].second;
  }

  if(need <= 0)
    printf("%d\n", res);
  else
    puts("-1");

  return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

4 21
10 8
7 4
3 1
5 4

Output

–

cmd

Demonstration

Codeforces Solution-C. Songs Compression-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 332 0