#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 5002
#define Gmax 10002

FILE *f = fopen ( "rucsac.in", "r" );
FILE *g = fopen ( "rucsac.out", "w" );

struct obiect{
    int val, weight;
}v[Nmax];

int D[2][Gmax];

int main(){
    int N, G;

    fscanf ( f, "%d%d", &N, &G );

    for ( int i = 1; i <= N; ++i )
        fscanf ( f, "%d%d", &v[i].weight, &v[i].val );

    int l = 0;
    for ( int i = 1; i <= N; ++i, l ^= 1 )
        for ( int j = v[i].weight; j <= G; ++j )
            D[l][j] = max ( D[l^1][j-v[i].weight] + v[i].val, D[l^1][j] );

    fprintf ( g, "%d", D[l^1][G] );

    return 0;
}