#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int v[3][10005];
int p[5005];
int w[5005];

int main()
{
    int n,g,i,j,l = 0;
    fin>>n>>g;
    for(i = 1; i <= n; i++){
        fin>>w[i]>>p[i];
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= g; j++){
            if(j >= w[i])
                v[l][j] = max(v[1-l][j],v[1-l][j-w[i]] + p[i]);
            else
                v[l][j] = v[1-l][j];
        }
        l = 1-l;
    }
    l = 1-l;
    fout<<v[l][g]<<endl;
    return 0;
}