#include <fstream>
using namespace std;
#define MAX(a, b) ((a > b) ? a : b)

short int G, N, W[5001], P[5001], T[2][10001];
ifstream input("rucsac.in");
ofstream output("rucsac.out");


int main(void)
{
    input >> N >> G;
    for(int i = 1; i <= N; i++)
        input >> W[i] >> P[i];

    int ok = 1;
    for(int i = 1; i <= N; i++, ok = 1 - ok)
        for(int j = G; j >= 1; j--)
        {
            if(j < W[i])
                T[ok][j] = T[1-ok][j];
            else
                T[ok][j] = MAX( T[1-ok][j], P[i] + T[1-ok][j-W[i]] );
        }
   
    output <<MAX(T[1][G], T[0][G]);
    output.close();
    input.close();
}