#include <iostream>
#include<fstream>
using namespace std;
int gr[5001],p[5001], cost[5001][10001];
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];
    for(i=1;i<=N;i++)
        for(g=0;g<=G;g++)
        {
            cost[i][g]=cost[i-1][g];
            if(gr[i]<=g)
                cost[i][g]=max(cost[i][g],cost[i-1][g-gr[i]]+p[i]);
        }
    h<<cost[N][G];
}