#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int NMAX=5005;
const int GMAX=10005;

int N, G, gr[NMAX], val[NMAX], dp1[GMAX], dp2[GMAX];

int main()
{
    fin>>N>>G;
    for(int i=1;i<=N;i++)
        fin>>gr[i]>>val[i];

    for(int i=1;i<=N;i++){
        for(int j=0;j<=G;j++){
            dp2[j]=dp1[j];
            if(gr[i]<=j)
                dp2[j]=max(dp2[j],dp1[j-gr[i]]+val[i]);
        }
        for(int j=0;j<=G;j++)
            dp1[j]=dp2[j];
    }

    fout<<dp1[G];

    return 0;
}