#include <stdio.h>
using namespace std;

int a[5001][10001],l,c;
int main()
{
    FILE * fin=fopen("rucsac.in","r");
    FILE * fout=fopen("rucsac.out","w");
    int n,C,i,j,d[5001],v[5001];
    fscanf(fin,"%d%d",&n,&C);
    for (i=1;i<=n;i++)
    {
        fscanf(fin,"%d%d",&d[i],&v[i]);
    }
    l=n; c=C;
    for (i=0;i<=l;i++)
    {
        for (j=0;j<=c;j++)
        {
            if (i==0 || j==0) a[i][j]=0;
            else if (d[i]>j) a[i][j]=a[i-1][j];
            else
            {
                if (a[i-1][j]>a[i-1][j-d[i]]+v[i]) a[i][j]=a[i-1][j];
                else a[i][j]=a[i-1][j-d[i]]+v[i];
            }
            //g<<a[i][j]<<" ";
        }
        //g<<'\n';
    }
    fprintf(fout,"%d",a[l][c]);
    /*i=l; j=c;
    while (a[i][j]!=0)
    {
        if (a[i-1][j]!=a[i][j])
        {
            g<<i<<" ";
            i--;
        }
        else i--;
        j-=d[i+1];
    }*/
    return 0;
}