#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int maxg=10001;
const int maxn=5000;
int R[maxg],N,G;
int W[maxn],P[maxn];
int main()
{
    int i,j,sol=0;
    f>>N>>G;
    for (i=1;i<=N;i++)
        f>>W[i]>>P[i];

    for (i=1;i<=N;i++)
        for (j=G-W[i];j>=0;j--)
            if (R[j+W[i]]<R[j]+P[i])
            {
                R[j+W[i]]=R[j]+P[i];
                sol=max(sol,R[j+W[i]]);
            }
    g<<sol;
}