#include<string.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include <fstream>
#define maxn 5001
#define maxG 10002
using namespace std;

int W[maxn],P[maxn],Optim[maxG];

ifstream f("rucsac.in");
ofstream r("rucsac.out");

int sol,i,j,N,G;

int main()
{
    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(Optim[j+W[i]]< Optim[j] + P[i])
                Optim[j+W[i]] = Optim[j] + P[i];

    for(i=0;i<=10001;++i)
        sol = max(sol,Optim[i]);


    r << sol;

    return 0;
}