#include <iostream>
#include <fstream>

#define maxN 5010
#define maxG 10010

using namespace std;

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

int n,gmax,price;
int g[maxN],p[maxN];
int d[maxN][maxG];

void readData()
{
    fin>>n>>gmax;
    for (int i=1; i<=n; ++i)
        fin>>g[i]>>p[i];
}

void PD()
{
    int line=0;
    for (int i=1; i<=n; ++i, line++)
        for (int cw=0; cw<=gmax; ++cw)
        {
            d[line+1][cw]=d[line][cw];
            if (g[i]<=cw)
                d[line+1][cw]=max(d[line+1][cw],d[line][cw-g[i]]+p[i]);
        }
    fout<<d[line][gmax];
}

int main()
{
    readData();
    PD();
    return 0;
}