#include <iostream>
#include <fstream>
using namespace std;

const int NR = 10005 ;

ifstream f ("rucsac.in") ;
ofstream g ("rucsac.out") ;

int t [ 2 ][ NR ] ;

int main() {
    
    int n , g ; f >> n >> g ;
    while ( n -- )
    {
        int x , y ; f >> x >> y ;
        for ( int i = 0 ; i + x <= g ; ++ i )    t [ ( n + 2 ) % 2 ][ i + x ] = max ( t [ ( n + 1 ) % 2 ][ i ] + y , t [ ( n + 1 ) % 2 ][ i + x ] ) ;
    }
    g << t [ 1 ][ g ] ;
	return 0;
}