#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int dp[3][5002];
vector<pair<int,int>>v;
int main(){
    ifstream cin("energii.in");
    ofstream cout("energii.out");
    int n,g,i,line=1,a,b,k;
    cin>>n>>g;
    for(i=1;i<=n;i++){
        cin>>a>>b;
        v.push_back(make_pair(a,b));
    }
    for(i=1;i<v[0].first;i++){
        dp[1][i]=0;
    }
    for(i=v[0].first;i<=1001;i++){
        dp[1][i]=v[0].second;
    }
    for(i=2;i<=n;i++){
        line=line%2+1;
        for(k=1;k<=1001;k++){
            if(k>=v[i-1].first)
            dp[line][k]=max(dp[line%2+1][k],dp[line%2+1][k-v[i-1].first]+v[i-1].second);
            else
            dp[line][k]=dp[line%2+1][k];
        }
    }
    cout<<dp[line][1001]-dp[line][g-1];
    return 0;
}