#include <bits/stdc++.h>
using namespace std;
long long dp[1000001];
int main() {
    int n,k;
    cin >> n >> k;
    long long a[100001],b[100001];
    for(int i = 1; i <= n; i++){
        cin >> b[i] >> a[i];
        b[i] = b[i] - a[i];
    }
    dp[0] = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = k - a[i]; j >= 0; j--){
            if(dp[j] > 0){
                dp[j + a[i]] = max(dp[j] + b[i], dp[j + a[i]]);
            }
        }
    }
    sort(dp,dp + 1 + k);
    cout << dp[k] - 1;
}