#include <iostream>
#include <fstream>
using namespace std;
struct obj{
    int g, v;
}x[5001];
int v[10001], cv[10001];
int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int i, j, n, m;
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>x[i].g>>x[i].v;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(x[i].g>j){
                cv[j]=v[j];
            }
            else{
                cv[j]=max(v[j-x[i].g]+x[i].v,v[j]);
            }
            //cout<<cv[j]<<' ';
        }
        //cout<<'\n';
        for(j=1;j<=m;j++){
            v[j]=cv[j];
        }
    }
    fout<<v[m]<<'\n';
    return 0;
}