#include <fstream>
#include <iostream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int MaxN = 5005, MaxG = 10005;
int n, gr[MaxN], cost[MaxN], d[MaxG], G;

int main()
{
    f >> n >> G;
    for (int i = 1; i <= n; i++)
    {
        f >> gr[i] >> cost[i];
    }
    int maxi = 0;
    d[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = maxi; j >= 0; j--) if(d[j] && j + gr[i] <= G)
        {
            d[j + gr[i]] = max(d[j + gr[i]], d[j] + cost[i]);
            maxi = max(maxi, j + gr[i]);
        }
    maxi = 0;
    for (int i = 0; i <= G; i++) maxi = max(maxi, d[i]);
    g << maxi - 1 << '\n';
    return 0;
}