#include<fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,gr,v[5555],g[5555],i,x[5555][11111],j;
int main(){
    fin>>n>>gr;
    for(i=1;i<=n;i++)
        fin>>g[i]>>v[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=gr;j++)
            if(g[i]<=j&&x[i-1][j-g[i]]+v[i]>x[i-1][j])
                x[i][j]=x[i-1][j-g[i]]+v[i];
            else
                x[i][j]=x[i-1][j];
    fout<<x[n][gr];
    return 0;
}