#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,g,i,j,best;
int prc[5010],wgt[5010],v[100010];
int main () {
    cin>>n>>g;
    for (i=1;i<=n;i++) {
        cin>>wgt[i]>>prc[i];
    }
    for (i=1;i<=n;i++) {
        for (j=g-wgt[i];j>=0;j--) {
            if (v[j+wgt[i]]<v[j]+prc[i]){
                v[j+wgt[i]]=v[j]+prc[i];
                if (v[j+wgt[i]]>best) {
                    best=v[j+wgt[i]];
                }
            }
        }
    }
    cout<<best;
}