#include <iostream>
#include <fstream>
using namespace std;
 
  long  a [ 10005 ];
  short n , g;
  int w [ 5005 ] , p [ 5005 ];
 
 
   int rucsac ( ){
       int i , j ;
       for ( i = 1 ; i <= n ; i++)
         for ( j = g ; j >= w [ i ] ; j--)
           a [ j ] = max ( a [ j ] , a [ j  - w[ i ]] + p [ i ]);
     return a [ g ];}
 
  int main() {
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
      cin >> n >> g;
     for ( int i = 1 ; i <= n ; i++)
       cin >> w [ i ] >> p [ i ];
     cout << rucsac();
}