#include <iostream>
#include <fstream>

using namespace std;

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

int n,g,i,j;
int v[2][10005];
int wt[10005];
int val[1005];

int main()
{
    in >>n>>g;
    for (i=1;i<=n;i++)
    {
        in >> wt[i];
        in >> val[i];
    }

    for (i=1;i<=n;i++)
    {
        for (j=0;j<=g;j++)
    {
        v[1][j]= v[1-1][j];
        if (wt[i]<=j)
        v[1][j]=max(val[i]+v[1-1][j-wt[i]],v[1][j]);
    }
        for (j=0;j<=g;j++)
        {
            v[0][j]=v[1][j];
        }
    }
    out << v[0][g];

}