#include<string.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include <fstream>
#define maxn 5001
#define maxG 10001
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];
                if(Optim[j+W[i]]>sol)
                    sol = Optim[j+W[i]];
            }
        }

    r << sol;

    return 0;
}