#include <fstream>
#include <vector>

using namespace std;

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

vector<int> profit, weight;
vector<vector<int>> dp;
int n, g;

int main() {
    cin >> n >> g;
    profit.resize(n + 2);
    weight.resize(n + 2);
    dp.resize(n + 2, vector<int>(g + 2, -1));
    for (int i = 1 ; i <= n ; ++i) {
        cin >> weight[i] >> profit[i];
    }
    dp[0][0] = 0;
    for (int i = 1 ; i <= n ; ++i) {
        for (int j = 0 ; j <= g ; ++j) {
            if (dp[i - 1][j] >= 0)
                dp[i][j] = dp[i - 1][j];
            if (j >= weight[i] && dp[i - 1][j - weight[i]] >= 0 && dp[i - 1][j - weight[i]] + profit[i] > dp[i][j])
                dp[i][j] = dp[i - 1][j - weight[i]] + profit[i];
        }
    }
    int ans;
    for (int j = 0 ; j <= g ; ++j) {
        ans = max(ans, dp[n][j]);
    }
    cout << ans;
    return 0;
}