#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int dp[3][10002];
vector<pair<int,int>>v;
int main(){
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n,g,i,line=0,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<=g;i++){
        dp[1][i]=v[0].second;
    }
    for(i=2;i<=n;i++){
        line=line%2+1;
        for(k=1;k<=g;k++){
            if(k>=v[i-2].first)
            dp[line%2+1][k]=max(dp[line][k],dp[line][k-v[i-2].first]+v[i-2].second);
            else
            dp[line%2+1][k]=dp[line][k];
        }
    }
    cout<<dp[line%2+1][g];
    return 0;
}