#include <fstream>
#include <algorithm>

using namespace std;

int n,G,g[5005],v[5005],d[2][10005];

inline void Read()
{
    int i;
    ifstream fin("rucsac.in");
    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>g[i]>>v[i];
    fin.close();
}

int main()
{
    int i,j,maxim;
    Read();
    for(i=1;i<=n;i++)
        for(j=1;j<=G;j++)
            if(j>=g[i])
                d[i%2][j]=max(d[(i-1)%2][j-g[i]] + v[i], d[(i-1)%2][j]);
    n=n%2;
    maxim=d[n][1];
    for(i=2;i<=G;i++)
        if(d[n][i]>maxim)
            maxim=d[n][i];
    ofstream fout("rucsac.out");
    fout<<maxim<<"\n";
    fout.close();
    return 0;
}