#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].second = a;
        v[i].first = b;
    }
    pd[v[1].second] = v[1].first;
    for (int i = 2;i<=n;++i)
    {
        for (int j = g - v[i].second; j>=0; --j)
            if (pd[j] && pd[j] + v[i].first > pd[j + v[i].second])
                pd[j + v[i].second] = pd[j] + v[i].first;
        pd[v[i].second] = max (pd[v[i].second], v[i].first);
    }
    int x = g;
    for (; !pd[x];--x);
    out << pd[x] << '\n';
    return 0;

}