#include <iostream>
#include <fstream>
#define DN 5002
using namespace std;
int n,G,i,j,mx,g[DN],v[DN],d[10002][DN];
int main()
{
    ifstream fin ("rucsac.in");
    ofstream fout ("rucsac.out");
    fin>>n>>G;
    for(i=1;i<=n;i++)
    {
        fin>>g[i]>>v[i];
    }
    for(i=0;i<=G;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i+g[j+1]<=G)
                d[i+g[j+1]][j+1]=max(d[i][j]+v[j+1],d[i+g[j+1]][j+1]);
            d[i][j+1]=max(d[i][j+1],d[i][j]);
        }
    }
    for(i=1;i<=G;i++)
    {
        if(d[i][n]>mx)mx=d[i][n];
    }
    fout<<mx<<"\n";
    return 0;
}