#include <fstream>
#define dim 5002
#define dim2 10002
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

long i,n,G,j,P[dim],w[dim],a[dim2],b[dim2];

int main(){

    f>>n>>G;
    for(i=1;i<=n;i++)
    f>>w[i]>>P[i];

    for(i=1;i<=n;i++){
        for(j=0;j<=G;j++){
            a[j]=b[j];
            if(w[i]<=j) a[j]=max(b[j],b[j-w[i]]+P[i]);
        }
        for(j=0;j<=G;j++) b[j]=a[j],a[j]=0;
    }
    g<<b[G];
}