#include<fstream>
#include<iostream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int W[10001],P[10001],sol[1][10001],N,G;

int main()
{

    in>>N>>G;
    int i,j;
    for(i = 1 ; i <= N ; i++)
        in>>W[i]>>P[i];
    int l = 0;
    for(i = 1 ; i <= N ;i++)
    {
        l = 1-l;
        for ( j = 0 ; j <= G ; j++)
    {

        sol[1-l][j] = sol[l][j];
        if(W[i] <= j)
            sol[1-l][j] = max(sol[1-l][j],sol[l][j-W[i]]+P[i]);
    }
    }
    out<<sol[1-l][G];
    in.close();
    out.close();
    return 0;
}