#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

vector<int> weights;
vector<int> prices;

int solve(int g, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(g + 1));

    for (int i = 0; i <= g; ++i)
        dp[0][i] = 0;

    for (int i = 0; i <= n; ++i)
        dp[i][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= g; ++j) {
            // Nu pun obiectul
            dp[i][j] = dp[i - 1][j];

            if (j - weights[i - 1] >= 0) {
                dp[i][j] = max(dp[i - 1][j - weights[i - 1]] + prices[i - 1], dp[i][j]);
            }
        }
    }

    return dp[n][g];
}

int main() {
    ifstream fin("rucsac.in");

    int g, n;
    fin >> n >> g;
    weights.resize(n);
    prices.resize(n);

    for (int i = 0; i < n; ++i) {
        fin >> weights[i] >> prices[i];
    }

    int result = solve(g, n);

    ofstream fout("rucsac.out");
    fout << result;

    return 0;
}