#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int NMAX=5000;
int dp[2][2*NMAX+5];
int main(){
    int n, g;
    fin>>n>>g;
    vector<pair<int,int> > obiecte(n+1);
    for(int i=1;i<=n;i++){
        fin>>obiecte[i].first>>obiecte[i].second;
    }
    int step=0;
    for(int i=1;i<=n;i++, step=1-step){
        for(int j=0;j<=g;j++){
            dp[step][j]=dp[1-step][j];
            if(obiecte[i].first<=j and dp[1-step][j-obiecte[i].first]+obiecte[i].second>dp[step][j]){
                dp[step][j]=dp[1-step][j-obiecte[i].first]+obiecte[i].second;
            }
        }
    }
    fout<<max(dp[0][g], dp[1][g]);
}