#include <fstream>
#include<algorithm>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,m,x[5002],y[5002],v[10002];
int main() {
    f>>n>>m;
    for(int i=1;i<=n;i++)
        fi>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=x[i];j--)
            v[j]=max(v[j],v[j-x[i]]+y[i]);
    fo<<v[m];
    return 0;
}