#include <iostream>
#include <fstream>

using namespace std;

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

struct element
{
    int greutate, valoare, indice;
};

element v[5001];
int a[10002];
int b[10002];




void sortVector(element v[], int n)
{
    bool sortat = false;
    while (!sortat)
    {
        sortat = true;
        for (int i = 1; i < n; i++)
        {
            if (v[i].greutate > v[i+1].greutate)
            {
                swap(v[i], v[i+1]);
                sortat = false;
            }
            else if (v[i].greutate == v[i+1].greutate && v[i].valoare > v[i+1].valoare)
            {
                swap(v[i], v[i+1]);
                sortat = false;
            }
        }
    }
}

void generareSolutie(int n, int gMax, element v[], int a[10002], int b[10002])
{
    for (int j = 1; j <= gMax; j++)
    {
        if (v[1].greutate > j) a[j] = 0;
        else a[j] = v[1].greutate;
    }

    for (int i = 2; i <= n; i++)
    {


        for (int j = 1; j <= gMax; j++)
        {


            if (i % 2 == 0)
            {
                if (v[i].greutate > j) b[j] = a[j];
                else b[j] = max(a[j], a[j-v[i].greutate] + v[i].valoare);
            }
            else
            {
                if (v[i].greutate > j) a[j] = b[j];
                else a[j] = max(b[j], b[j-v[i].greutate] + v[i].valoare);
            }

        }

    }

}

int main()
{
   int n, gMax;
   fin >> n >> gMax;

   for (int i = 1; i <= n; i++)
   {
       fin >> v[i].greutate >> v[i].valoare;
       v[i].indice = i;
   }

    sortVector(v, n);
    generareSolutie(n, gMax, v, a, b);

    /*for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= gMax; j++)
            cout << a[i][j] <<" ";
        cout << endl;
    }*/

    if (n % 2 == 0) fout << b[gMax];
    else fout <<a[gMax];
}