#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int main()
{
    int n,Gmax,g[3005],v[5005],C[3005][10005],i,j;
    fi>>n>>Gmax;
    for(i=1;i<=n;i++){
        fi>>g[i]>>v[i];
    }
    for(i=0;i<=n;i++){
        C[i][0]=0;
    }
    for(j=0;j<=Gmax;j++){
        C[0][j]=0;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=Gmax;j++){
            if(g[i]>j||C[i-1][j-g[i]]+v[i]<C[i-1][j])
                C[i][j]=C[i-1][j];
            else
                C[i][j]=C[i-1][j-g[i]]+v[i];
        }
    }
//    for(i=1;i<=n;i++){
//            cout<<'\n';
//        for(j=1;j<=Gmax;j++){
//            cout<<C[i][j]<<" ";
//        }
//    }
fo<<C[n][Gmax];

}