#include<fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout("rucsac.out");
int D[10010],g[5010],p[5010];
int N,G,i,j,sol;
int main () {
    fin>>N>>G;
    for(i=1;i<=N;i++)
        fin>>g[i]>>p[i];
    D[0]=1;
    for (i=1;i<=N;i++)
        for (j=G;j>=0;j--)
            if (D[j]!=0 && j+g[i]<=G) {
                D[j+g[i]]= max(D[j+g[i]],D[j]+p[i]);
                sol= max(sol,D[j+g[i]]);
            }
    for(i=1;i<=G;i++)
        sol=max(sol,D[i]);
    fout<<sol-1;
    return 0;
}