#include <bits/stdc++.h>
using namespace std;

int dp[2][10005], w[10005], p[10005];

int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n, g;
    cin >> n >> g;
    for (int i = 1; i <= n; ++i)
        cin >> w[i] >> p[i];

    int line = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= g; ++j)
            dp[line][j] = 0;

        for (int j = 0; j <= g; ++j)
        {
            dp[line][j] = dp[1-line][j];
            if (j >= w[i])
                dp[line][j] = max(dp[line][j], dp[1-line][j-w[i]] + p[i]);
        }

        line = 1 - line;
    }

    cout << dp[1-line][g];

    return 0;
}