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

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

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];
    }
    g<<a[G];
}