#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int N,G,W[5005],P[5005],d[2][10005];
int main()
{
    in>>N>>G;
    int i,j,cw;
    for(i=1,j=1;j<=N;j++,i=!i)
    {
        in>>W[i]>>P[i];
        for(cw=1;cw<=G;cw++)
        {
            d[i][cw] = d[!i][cw];
            if(W[i] <= cw)
                d[i][cw] = max(d[i][cw], d[!i][cw - W[i]] + P[i]);
        }
    }
    out<<d[N%2][G]<<'\n';
}