#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("ruscac.in");
ofstream fout ("rucsac.out");

int gr[10002],pre[10002];
int v1[10002];
int v2[10002];


int main()
{
    int linie=1;
    int n,g;
    fin>>n>>g;
    for(int k=1;k<=n;k++)
        fin>>gr[k]>>pre[k];
    for(int elem=1;elem<=n;elem++)
    {
        if(linie==1)
        {
            linie=2;
            for(int grec=0;grec<=g;grec++)
            {
                v1[grec]=v2[grec];
                if(gr[elem]<=grec)
                    v1[grec]=max(v1[grec],v2[grec-gr[elem]]+pre[elem]);
            }
        }
        else
        {
            linie=1;
            for(int grec=0;grec<=g;grec++)
            {
                v2[grec]=v1[grec];
                if(gr[elem]<=grec)
                    v2[grec]=max(v2[grec],v1[grec-gr[elem]]+pre[elem]);
            }
        }

    }
    if(linie==1)
        fout<<v2[g];
    else
        fout<<v1[g];
    return 0;
}