#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream gout("rucsac.out");
int a[2][10001],n,gmax,g[5001],p[5001];
void citire()
{
    f>>n>>gmax;
    for (int i=1;i<=n;i++)
    {
        f>>g[i]>>p[i];
    }
}
void rez()
{
    /*
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=gmax;j++)
        {
            if (j>=g[i])
            {
                a[i][j]=max(a[i-1][j],a[i-1][j-g[i]]+p[i]);
            }
            else a[i][j]=a[i-1][j];
        }
    }
    */
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=gmax;j++)
        {
            if (j-g[i]>=0)
            {
                a[2][j]=max(a[1][j],a[1][j-g[i]]+p[i]);
            }
            else
            {
                a[2][j]=a[1][j];
            }
        }
        for (int j=1;j<=gmax;j++)
        {
            a[1][j]=a[2][j];
        }
    }
    g<<a[2][gmax];
    /*
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=gmax;j++)
        {
            gout<<a[i][j]<<" ";
        }
        gout<<"\n";
    }
    */
    gout<<a[n][gmax];
}
int main()
{
    citire();
    rez();
    return 0;
}