#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2000000000
#define MaxN 10005
using namespace std;
     
FILE *IN,*OUT;
int N,G,val,w,v[MaxN],Max;
int main()
{
    IN=fopen("rucsac.in","r");
    OUT=fopen("rucsac.out","w");
     
    fscanf(IN,"%d%d",&N,&G);
    v[0]=1;
    for(int i=1;i<=N;i++)
    {
        fscanf(IN,"%d%d",&w,&val);
        for(int j=G-w;j>=0;j--)
            if(v[j])
                v[j+w]=max(v[j+w],v[j]+val),Max=max(v[j+w],Max);
    }
    fprintf(OUT,"%d",Max-1);
    return 0;
}