#define fisier "rucsac"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");

const int
N = 5000,
G = 10000 + 1;

int
n, g,
_a[G],   _b[G],
*a = _a, *b = _b;

int main()
{
    in >> n >> g;

    while (n--)
    {
        int w, p;
        in >> w >> p;

        for (int i = 0; i <= g; i++)
             if (i < w || b[i - w] + p < b[i])
                a[i] = b[i];
             else
                a[i] = b[i - w] + p;

        std::swap(a, b);
    }

    out << b[g];
}