#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int a[5001][10001],l,c;
int main()
{
    int n,C,i,j,d[5001],v[5001];
    f>>n>>C;
    for (i=1;i<=n;i++)
    {
        f>>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';
    }
    g<<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;
}