// Problema rucsacului, dinamica O(N*G) timp, O(N*G) memorie

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
#define MAXN 5010
#define MAXG 10010

int N, G, Pmax;
int greutate[MAXN], profit[MAXN];
int D[2][MAXG];

int main()
{
    in >> N >> G ;
    for ( int i = 1 ; i <= N ; ++ i )
            in >> greutate[i] >>profit[i];
int l = 0 ;
    for ( int i = 1 ; i <= N ; ++i , l=1-l)
    {
        for ( int cw = 0 ; cw <= G ; ++ cw)
           {

            D[1-l][cw] = D[l][cw];
        if (greutate[i]<=cw)
               D[1-l][cw] = max (D[1-l][cw], D[l][cw-greutate[i]] + profit [i]);

           }
    }
out << D[l][G];


    return 0;
}