#include <iostream>
#include <fstream>

using namespace std;
int n,G,k,greu[10004],profit[10004],a[2][10005],sol;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int main()
{
    f>>n>>G;
    for(int i=1; i<=n; i++)
        f>>greu[i]>>profit[i];
    k=0;
    for(int i=1; i<=n; i++ , k=1-k)
        for(int j=0; j<=G; j++)
        {
            a[1-k][j]=a[k][j];
            if(greu[i]<=j)a[1-k][j]=max(a[1-k][j],a[k][j-greu[i]]+profit[i]);
        }
    sol=a[k][G];
    g<<sol;
    return 0;
}