#include <fstream>
using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int gr[5010], val[5010], n, gmax, i, j, a[3][10010], li, k;

int main()
{
    fin>>n>>gmax;

    for (i=1; i<=n; i++)
        fin>>gr[i]>>val[i];

    li=1;
    for (i=1; i<=n; i++)
    {
        if (i>1)
            li=2;

        for (j=0; j<=gmax; j++)
        {
            if (gr[i]>j)
                a[li][j]=a[li-1][j];
            else
            {
                if (a[li-1][j-gr[i]]+val[i]>a[li-1][j])
                    a[li][j]=a[li-1][j-gr[i]]+val[i];
                else
                    a[li][j]=a[li-1][j];
            }
        }

            for (k=0; k<=gmax; k++)
                a[li-1][k]=a[li][k];

    }

    fout<<a[2][gmax];

    fin.close();
    fout.close();
    return 0;
}