#include <iostream>
#include<fstream>
using namespace std;
int gr[5010],p[5010],cost[10010];
int main()
{
    int N,G,i,j,g;
    fstream f,h;
    f.open("rucsac.in",ios::in);
    h.open("rucsac.out",ios::out);
    f>>N>>G;
    for(i=1;i<=N;i++)
        f>>gr[i]>>p[i];
    int sol=0;
    for(i=1;i<=N;i++)
        for(g=G-gr[i];g>=0;g--)
        {
            if(cost[g+gr[i]]<cost[g]+p[i])
                cost[g+gr[i]]=cost[g]+p[i];
            if(cost[g+gr[i]]>sol)
                sol=cost[g+gr[i]];
        }
    h<<sol;
}