n, m = list(map(int,input().split()))
myList = []
for _ in range(n):
myList.append(list(map(int,input().split())))
mySumCom = 0
mySumUnCom = 0
mySubList = []
for i in myList:
mySumCom += i[1]
mySumUnCom += i[0]
mySubList.append(i[0]-i[1])
if mySumCom > m:
print(-1)
exit()
else:
mySub = mySumUnCom - m
mySum = 0
if m >= mySumUnCom:
print(0)
exit()
mySubList.sort(reverse = True)
for i,v in enumerate(mySubList):
mySum += v
if mySum >= mySub:
print(i+1)
exit()
#include <stdio.h>
typedef long long ll;
struct disk{
ll ori;
ll comp;
};
void merge(disk arr[], int kiri, int tengah, int kanan){
int a = tengah - kiri + 1;
int b = kanan - tengah;
disk k1[a], k2[b];
for (int i = 0; i < a; i++){
k1[i] = arr[kiri + i];
}
for (int j = 0; j < b; j++){
k2[j] = arr[tengah + 1 + j];
}
int l = 0, m = 0, n = kiri;
while (l < a && m < b){
if (k1[l].ori - k1[l].comp >= k2[m].ori - k2[m].comp){
arr[n] = k1[l];
l++;
} else {
arr[n] = k2[m];
m++;
}
n++;
}
while (l < a){
arr[n] = k1[l];
l++;
n++;
}
while (m < b){
arr[n] = k2[m];
m++;
n++;
}
}
void mergeSort(disk arr[], int kiri, int kanan){
if (kiri < kanan){
int tengah = kiri + (kanan - kiri) / 2;
mergeSort(arr, kiri, tengah);
mergeSort(arr, tengah + 1, kanan);
merge(arr, kiri, tengah, kanan);
}
}
int main(){
int n;
ll size;
ll sum = 0;
scanf("%d %lld", &n, &size);
disk ivan[n];
for (int i = 0; i < n; i++){
scanf("%lld %lld", &ivan[i].ori, &ivan[i].comp);
sum += ivan[i].ori;
}
mergeSort(ivan, 0, n - 1);
int flag = 0;
for (int i = 0; i <= n; i++){
if (sum <= size){
printf("%d", i);
flag = 1;
break;
}
sum -= (ivan[i].ori - ivan[i].comp);
}
if (flag == 0){
printf("-1");
}
}
162. Find Peak Element | 1529A - Eshag Loves Big Arrays |
19. Remove Nth Node From End of List | 925. Long Pressed Name |
1051. Height Checker | 695. Max Area of Island |
402. Remove K Digits | 97. Interleaving String |
543. Diameter of Binary Tree | 124. Binary Tree Maximum Path Sum |
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts | 501A - Contest |
160A- Twins | 752. Open the Lock |
1535A - Fair Playoff | 1538F - Interesting Function |
1920. Build Array from Permutation | 494. Target Sum |
797. All Paths From Source to Target | 1547B - Alphabetical Strings |
1550A - Find The Array | 118B - Present from Lena |
27A - Next Test | 785. Is Graph Bipartite |
90. Subsets II | 1560A - Dislike of Threes |
36. Valid Sudoku | 557. Reverse Words in a String III |
566. Reshape the Matrix | 167. Two Sum II - Input array is sorted |