#include <iostream>
#include<fstream>
#include<iomanip>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,gmax,g[5005],v[5005],m[5005][10005];

void citire()
{
  int i;
  fin>>n>>gmax;
  for(i=1;i<=n;i++)
     fin>>g[i]>>v[i];
}

int maxi(int x,int y)
{
    if(x>=y)
      return x;
      else
        return y;
}

void formare()
{
    int i,j;
    for(i=1;i<=n;i++)
       for(j=1;j<=gmax;j++)
       { m[i][j]=m[i-1][j];
           if(g[i]<=j)
           m[i][j]=maxi( m[i-1][j] , v[i]+m[i-1][j-g[i]] );

       }
}


int main()
{
   citire();
   formare();
   int i,j;
   fout<<m[n][gmax];
    return 0;
}