#include <fstream>
#include <climits>
using namespace std;
long long sol[1010];
long long g[1010];
long long v[1010];
long long i,j,n,G,Max;

int main() {
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    fin>>n>>G;
    for (i=1;i<=n;i++) {
        fin>>g[i]>>v[i];
    }
    for (i=1;i<=G;i++) {
        sol[i]=-1;
    }
    for (i=1;i<=n;i++) {
        for (j=G;j>=0;j--) {
            if (sol[j]!=-1) {
                if (j+g[i]<=G) {
                    sol[j+g[i]]=sol[j]+v[i];
                }
            }
        }
    }
    Max=LLONG_MIN;
    for (i=1;i<=G;i++) {
        Max=max(Max,sol[i]);
    }
    fout<<Max;
    return 0;
}