#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int n,g,cmax[10005],w[5005],p[5005];
    in >> n >> g;
    for (int i = 1; i <= n; i++)
        in >> w[i] >> p[i];
    for (int i = 1; i <= g; i++)
        cmax[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = g - w[i]; j >= 0; j--)
        {
            cmax[j + w[i]] = max(cmax[j + w[i]],p[i] + cmax[j]);
        }
    }
    out << cmax[g];
    return 0;
}