#include <bits/stdc++.h>

using namespace std;

int main()
{
    ifstream f("rucsac.in");
    ofstream c("rucsac.out");
    int n=0, G=0, x=0;
    f>>n>>G;
    int d[2][10002] = {};
    int g[5002]={};
    int val[5002]={};
    for(int i=1; i<=n; ++i) f>>g[i]>>val[i];
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=G; ++j){
            if(j < g[i]) d[i&1][j] = d[(i-1)&1][j];
            else d[i&1][j]=max(d[(i-1)&1][j], d[(i-1)&1][j-g[i]] + val[i]);
           x=d[i&1][j];}}
    c<<x;
    return 0;
}