#include <bits/stdc++.h>
#define GMAX 10001
#define NMAX 5001
using namespace std;

string file="rucsac";

ifstream fin(file+".in");
ofstream fout(file+".out");

int n,gmax;
int sol[2][GMAX];
int v[NMAX],g[NMAX];

int main()
{
    int i,j,l;
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
    {
        fin>>g[i]>>v[i];
    }
    l=0;
    for(i=1;i<=n;++i,l=1-l)
    {
        for(j=0;j<=gmax;++j)
        {
            sol[1-l][j]=sol[l][j];
            if(g[i]<=gmax)
            {
                sol[1-l][j]=max(sol[1-l][j],sol[l][j-g[i]]+v[i]);
            }
        }
    }
    fout<<sol[l][gmax];
    return 0;
}