#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define NMAX 5005
#define GMAX 10005
int N,G;
int W[NMAX],P[NMAX],D[2][GMAX];
int main()
{
    fin>>N>>G;
    for (int i=1;i<=N;i++)
        fin>>W[i]>>P[i];
    int l=0;
    for (int i=1;i<=N;i++,l=1-l)
    {
        for (int g=0;g<=G;g++)
        {
            D[1-l][g] = D[l][g];
            if (W[i]<=g)
            {
                D[1-l][g]=max(D[1-l][g],D[l][g-W[i]]+P[i]);
            }
        }
    }
    fout<<D[l][G]<<'\n';
    return 0;
}