#include <bits/stdc++.h>

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

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

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

int main() {
    fin >> N >> G;
    int i=1;
    
    while( i <= N ) {
        fin >> 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]);    
        }
    }
    fout  << b[N][G];
   return 0;
}