#include <fstream>
#include <vector>
#define maxn 5010
#define maxg 10010
using namespace std;


ifstream f("rucsac.in");
ofstream g("rucsac.out");
vector<int> p(maxn),w(maxn);
int n,G;
int D[maxn][maxg];
int main()
{
 int i, j;
    f>>n>>G;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
        for(i=1;i<=n;i++)
            for(j=0;j<=G;j++)
        {
            D[i][j]=D[i-1][j];
             if(w[i]<=j)
                D[i][j]=max(D[i][j],D[i-1][j-w[i]]+p[i]);
        }
        g<<D[n][G];

}