#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N, G;
long long res[10004];
struct s {
    int w, p;
} v[5004];

long long solve(int i) {
    if(i==N)
        return max(res[G-v[i].w]+v[i].p, res[G]);
    for(int j=G;j>=1;j--)
        if(v[i].w<=j)
            res[j]=max(res[j-v[i].w]+v[i].p, res[j]);
    solve(i+1);
}

int main() {
    f>>N>>G;
    for(int i=1;i<=N;i++)
        f>>v[i].w>>v[i].p;
    g<<solve(1);


    f.close();
    g.close();
    return 0;
}