#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[1009][1009];
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[i][j] = d[i-1][j];

            if(j - a[i].g >= 0){
                d[i][j] = max(d[i-1][j],d[i-1][j-a[i].g] + a[i].p);
            }
        }
    }

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