#include <iostream>
#include <cstdio>

using namespace std;

#define n_max 5005
#define g_max 10005

int n,g,w[n_max],p[n_max],sol[g_max];

void read()
{
    scanf( "%d %d" , &n , &g ) ;
    for ( int i = 1 ; i <= n ; i ++ )
        scanf( "%d %d" , &w[i] , &p[i] ) ;
}

void dynamic()
{
    for ( int i = 1 ; i <= n ; i ++ )
        for ( int j = g ; j >= w[i] ; j -- )
            sol[j] = max( sol[j] , sol[j-w[i]] + p[i] ) ;
}

int main()
{
    freopen( "rucsac.in" , "r" , stdin ) ;
    freopen( "rucsac.out" , "w" , stdout ) ;
    read() ;
    dynamic() ;
    printf( "%d\n" , sol[g] ) ;
    return 0;
}