#include <iostream>

using namespace std;

int b[5000][10000],N,G,a[5000],c[5000];

int max(int a,int b)
 {
      if(a>b) return a;
      else return b;
 }

int main()
{
    ifstream fi("rucsac.in");
    ofstream fo("rucsac.out");
    
    fi>>N>>G;
    int i=1;
    int j=1;
    
    while( i <= N ) {
        fi>>a[i]>>c[i];
        i++;
    }
   
    for(int i=1;i<=N;i++) 
    { 
    b[i][0]=0;
    }
    for(int j=1;j<=G;j++) 
    { 
        b[0][j]=0; 
    }
    
    for(int i=1;i<=N;i++) {
                            for(int j=1;j<=G;j++) { 
                                                    if(j<a[i]) { 
                                                                 b[i][j]=b[i-1][j]; } else {
                                                                                            b[i][j]= max(b[i-1][j],b[i-1][j-a[i]]+c[i]);
                                                                                           }
                                                  }
                            }
    
fo<<b[N][G];
}