#include <stdio.h>
#include <algorithm>
#define maxn 5001
#define maxg 10001
using namespace std;
int w[maxn],p[maxn],x[maxg],n,g;
int main() {
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&g);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&w[i],&p[i]);
    int sol=0;
    x[0]=0;
    for(int i=1;i<=n;++i)
        for(int j=g-w[i];j>=0;--j)
            if(x[j+w[i]]<x[j]+p[i]){
                x[j+w[i]]=x[j]+p[i];
                if(x[j+w[i]]>sol)
                    sol=x[j+w[i]];
            }
    printf("%d",sol);
    return 0;
}