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

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N, G, Pmax;
int W[5010], P[5010];
int D[2][10010];

int main()
{



    fin >> N >> G;
    for (int i = 1; i <= N; ++i)
        fin >>W[i]>>P[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 (W[i] <= cw)
                D[1 - l][cw] = max(D[1 - l][cw], D[l][cw - W[i]] + P[i]);
        }


    Pmax = D[l][G];


    fout << Pmax;

    return 0;
}