#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

struct str
{
    int g;
    int v;
};

str a[5002];
int b[2][10002];

int n,g;

void copiere()
{
    int i;
    for(i=1;i<=g;i++)
        b[0][i]=b[1][i];
}

int main()
{
    int i,j;
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>a[i].g>>a[i].v;
    for(i=1;i<=n;i++){
        for(j=1;j<=g;j++)
            {
                if(a[i].g>j)
                    b[1][j]=b[0][j];
                else
                    b[1][j]=max(b[0][j],b[0][j-a[i].g]+a[i].v);
            }
        copiere();
    }
    fout<<b[1][g]<<"\n";
    fin.close();
    fout.close();
    return 0;
}