#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//0-1 Knapsack: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
void printDP(const int n, const int c, vector<vector<int> >& dp){
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= c; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}

int solve_a(const int n, const int c, const vector<int>& v, const vector<int>& w) {
    
    vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= c; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= w[i - 1]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }
    //printDP(n, c, dp);
    return dp[n][c];
}

int solve_a_1(const int n, const int c, const vector<int>& v, const vector<int>& w) {
    vector<int> dp(c + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = c; j > 0; j--) {
            if (j >= w[i]) {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }
    return dp[c];
}

int solve_a_2(const int n, const int c, const vector<int>& v, const vector<int>& w) {
    vector<vector<int>> dp(2, vector<int>(c + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= c; j++) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            if (j >= w[i - 1]) {
                dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - w[i - 1]] + v[i - 1]);
            }
        }
    }
    //printDP(n, c, dp);
    return dp[n % 2][c];
}

int solve_b(const int n, const int c, const vector<int>& v, const vector<int>& w) {
    
    vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= c; j++) {
            dp[i][j] = dp[i + 1][j];
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
    }
    //printDP(n, c, dp);
    return dp[0][c];
}


int solve_c_rec(int i, int j, vector<vector<int>>& dp,
        const vector<int>& v, const vector<int>& w) {
    if (i == 0 || j == 0) {
        return 0;
    }
    if (dp[i][j] != -1) {
        return dp[i][j];
    }
    int result = solve_c_rec(i - 1, j, dp, v, w);
    if (j >= w[i - 1]) {
        result = max(result, solve_c_rec(i - 1, j - w[i - 1], dp, v, w) + v[i - 1]);
    }
    dp[i][j] = result;
    return result;   
}

int solve_c(const int n, const int c, const vector<int>& v, const vector<int>& w) {
    vector<vector<int>> dp(n + 1, vector<int>(c + 1, -1));
    return solve_c_rec(n, c, dp, v, w);
}

int solve_d_rec(int i, int j, vector<vector<int>>& dp, const int n,
        const vector<int>& v, const vector<int>& w) {
    if (i == n || j == 0) {
        return 0;
    }
    if (dp[i][j] != -1) {
        return dp[i][j];
    }
    int result = solve_d_rec(i + 1, j, dp, n, v, w);
    if (j >= w[i]) {
        result = max(result, solve_d_rec(i + 1, j - w[i], dp, n, v, w) + v[i]);
    }
    dp[i][j] = result;
    return result;   
}

int solve_d(const int n, const int c, const vector<int>& v, const vector<int>& w) {
    vector<vector<int>> dp(n + 1, vector<int>(c + 1, -1));
    return solve_d_rec(0, c, dp, n, v, w);
}

int main() {
    int n, c;
    cin >> n >> c;
    vector<int> v(n, 0);
    vector<int> w(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> w[i];
    }
    int ans = solve_a_2(n, c, v, w);
    cout << ans << endl;
}

Measured memory_bytes: 3220