#include <fstream>

using namespace std;

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

const int NMAX = 1e4 + 5;

int dp[NMAX / 2][NMAX];
int w[NMAX / 2], p[NMAX / 2];

int solve(int n, int g)
{
    int s = 0;
    for (int i = 1; i <= g; i++)
        dp[0][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int cap = 0; cap <= g; cap++)
        {
            if (cap - w[i] >= 0)
            {
                dp[i][cap] = max(dp[i - 1][cap], dp[i - 1][cap - w[i]] + p[i]);
            }
            else
                dp[i][cap] = dp[i - 1][cap];
        }
    }
    return dp[n][g];

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, g, i;
    cin >> n >> g;
    for (i = 1; i <= n; i++)
        cin >> w[i] >> p[i];
    cout << solve(n, g);
    return 0;
}