#include <iostream>
#include <fstream>

using namespace std;

const int gmax=10000;
const int nmax=5000;

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

int d[gmax+5],last[gmax+5],v[nmax+5],g[nmax+5];

int main()
{
    int n,G;
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>v[i];

    d[0]=1;
    int mx=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=min(mx,G-g[i]);j>=0;--j)
        {
            if(d[j]&&d[j+g[i]]<d[j]+v[i])
            {
                d[j+g[i]]=d[j]+v[i];
                last[j+g[i]]=i;
                if(mx<j+g[i])
                    mx=j+g[i];

            }
        }
    }

    mx=d[1];
    for(int i=2;i<=G;i++)
        if(mx<d[i])
            mx=d[i];

    fout<<mx-1;
    return 0;
}