#include <iostream>
#include <fstream>
#include <algorithm>
#define Nmax 5001
#define Gmax 100001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N,G;
int W[Nmax],P[Nmax],DP[3][Gmax];

void read()
{
     fin>>N>>G;
    for(int i=1;i<=N;++i)
        fin>>W[i]>>P[i];
}

void solve()
{
    int i,j;
   int k=1;
    for(i=1;i<=N;i++)
    {
         for(j=0;j<=G;j++)
        {

            if(W[i]<=j)
              DP[k][j]=max(DP[k-1][j],DP[k-1][j-W[i]]+P[i]);
              else
            DP[k][j]=DP[k-1][j];

        }
        if(k==1) k=2;
        else k=1;
    }

if(k==1) fout<<DP[2][G];
else fout<<DP[1][G];
}

int main()
{

    read();
    solve();
    return 0;
}