#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct obiect
{
    int w,p;
};obiect v[5007];

int d[5007] ;

int main()
{
    freopen ("rucsac.in" , "r" , stdin );
    freopen ("rucsac.out" , "w" , stdout );
    int n , g ;
    int profit=0 ;
    scanf ("%d%d" , &n , &g ) ;
    for ( int i = 1 ; i <= n ; ++i )
        scanf ("%d%d" , &v[i].w , &v[i].p ) ;
    d[0]=1;
    for ( int i = 1 ; i <= n ; ++i )
        for ( int j = g ; i >= 1 ; --i )
            if( d[j] and (j+v[i].w)<=g )
                d[j+v[i].w]=max(d[j+v[i].w],(d[j]+v[i].p));
    int maxi=0;
    for ( int i = 1 ; i <= n ; ++i )
        if (d[i]>maxi)maxi=d[i];
    printf ("%d\n" , maxi-1 ) ;
    return 0;
}