#include <iostream>
#include <fstream>
#define MAXN 5001
#define MAXG 10001

using namespace std;

int a,n,gr,greutate[MAXN],profit[MAXN],pmax[MAXG],pimax[MAXG],profmax;

int main()
{
    ifstream f ("rucsac.in");
    ofstream g ("rucsac.out");
    f>>n>>gr;
    for(int i=1;i<=n;i++)
      f>>greutate[i]>>profit[i];
    for(int i=1;i<=n;i++)
      for(int j=gr;j>=1;j--){
        if(j>=greutate[i])pmax[j]=max(pimax[j],pimax[j-greutate[i]]+profit[i]);
        else pmax[j]=pimax[j];
        pimax[j]=pmax[j];
      }
    for(int i=1;i<=gr;i++)
      if(pmax[i]>=profmax)
        profmax=pmax[i];
    g<<profmax;
    f.close ();
    g.close ();
    return 0;
}