#include <fstream>
#include <iostream>
using namespace std;
int a[10001],n,g,i,j,max1,PROFIT[10001];
long long p[10001];
char fr[10001];
ofstream gg("rucsac.out");
int main()
{
    freopen("rucsac.in","r",stdin);
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;i++)
        scanf("%d%d",&a[i],&PROFIT[i]);
    int max1=0;
    fr[0]=1;
    for(i=1;i<=n;i++)
    for(j=max1;j>=0;j--){
        if(fr[j]==1&&j+a[i]<=g&&p[j+a[i]]<p[j]+PROFIT[i])
            {fr[j+a[i]]=1;
            p[j+a[i]]=p[j]+PROFIT[i];}
        max1=max1+a[i];
    }
    max1=0;
    for(i=1;i<=g;i++)
        if(p[i]>max1)
        max1=p[i];
    gg<<max1;
    return 0;
}