#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

struct asd{
    int g,p;
}a[1009];
int N,G,i,j;
int d[2][1008];
int main()
{
    f >> N >> G;
    for(i = 1; i <= N; i++){
        f >> a[i].g >> a[i].p;
    }
    for(i = 1; i <= N; i++){
        for(j = 1; j <= G; j++){
            d[2][j] = d[1][j];
            if(j - a[i].g >= 0){
                d[2][j] = max(d[1][j] , d[1][j-a[i].g] + a[i].p);
            }
        }
        for(j = 1; j <= G; j++){
            d[1][j] = d[2][j];
            d[2][j] = 0;
        }
    }

    g << d[1][G];
    return 0;
}