#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++)
        {
            d[i%2][j]=d[(i-1)%2][j];
            if(j>=g[i] && d[(i-1)%2][j-g[i]] + v[i]>d[i%2][j])
                d[i%2][j]=d[(i-1)%2][j-g[i]] + v[i];
        }
    n=n%2;
    maxim=d[n][1];
    for(i=2;i<=G;i++)
        maxim=max(maxim, d[n][i]);
    ofstream fout("rucsac.out");
    fout<<maxim<<"\n";
    fout.close();
    return 0;
}