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

using namespace std;

int a,n,gr,greutate[MAXN],profit[MAXN],pmax[2][MAXG],profmax,ic,ip;

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--){
        ic=i%2;ip=(i-1)%2;
        if(j>=greutate[i])pmax[ic][j]=max(pmax[ip][j],pmax[ip][j-greutate[i]]+profit[i]);
        else pmax[ic][j]=pmax[ip][j];
      }
    for(int i=1;i<=gr;i++)
      profmax=max(profmax,pmax[n%2][i]);
    g<<profmax;
    f.close ();
    g.close ();
    return 0;
}