#include <stdio.h>

using namespace std;
FILE* f;
FILE* g;
struct item{
    int w;
    int v;
}a[5001];
int b[10001],n,s;
void read(){
    fscanf(f,"%d %d",&n,&s);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d %d",&a[i].w,&a[i].v);
}
void solve(){
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=s-a[i].w;j>=0;j--){
            if(b[j+a[i].w]<b[j]+a[i].v){
                b[j+a[i].w]=b[j]+a[i].v;
                if(ans<b[j+a[i].w]) ans=b[j+a[i].w];
            }
    }
    /*for(int k=0;k<=s;k++)
        fprintf(g,"%d ",b[k]);
    fprintf(g,"\n");*/

    }
    fprintf(g,"%d ",ans);
}
int main()
{
    f=fopen("rucsac.in","r");
    g=fopen("rucsac.out","w");
    read();
    solve();
    return 0;
}