#include <bits/stdc++.h>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
int pd[10001];
pair <int , int> v[5001];
int main ()
{
    int n, g;
    in >> n >> g;
    for (int i = 1;i <= n;++i)
    {
        int a, b;
        in >> a >> b;
        v[i].first = a;
        v[i].second = b;
    }
    pd[v[1].first] = v[1].second;
    for (int i = 2;i<=n;++i)
    {
        for (int j = g - v[i].first; j>=0; --j)
            if (pd[j] && pd[j] + v[i].second > pd[j + v[i].first])
                pd[j + v[i].first] = pd[j] + v[i].second;
        pd[v[i].first] = max (pd[v[i].first], v[i].second);
    }
    int rez = 0;
    for (int i = 1; i<=g;++i)
        rez = max (rez, pd[i]);
    out << rez << '\n';
    return 0;

}