#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int NMAX=5000;
int dp[NMAX+5][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;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=g;j++){
            dp[i][j]=dp[i-1][j];
            if(obiecte[i].first<=j and dp[i-1][j-obiecte[i].first]+obiecte[i].second>dp[i][j]){
                dp[i][j]=dp[i-1][j-obiecte[i].first]+obiecte[i].second;
            }
        }
    }
    fout<<dp[n][g];
}