#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, ans = -1;

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