#include <fstream>

using namespace std;

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

const int max_size = 1e4 + 1;

int dp[max_size];

int main ()
{
    int n, g, ans = 0;
    in >> n >> g;
    for (int i = 1; i <= n; i++)
    {
        int w, cost;
        in >> w >> cost;
        for (int j = g - w; j >= 0; j--)
        {
            dp[j + w] = max(dp[j + w], dp[j] + cost);
            ans = max(ans, dp[j + w]);
        }
    }
    out << ans;
    in.close();
    out.close();
    return 0;
}