#include <iostream>
#include <vector>
using namespace std;

const int N = 1e4 + 10;
int v[N], w[N], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    vector<vector<int>> memo(n+1, vector<int>(m+1, -1)); // 下标从 1 开始，-1 代表没有被计算过

    auto dfs = [&](auto&& dfs, int i, int j) -> int { // 代表还有前i个物品没有选择，余下体积为j的最大价值

        if (i <= 0) return 0; // 下标从 1 开始，如果 <= 0 说明没得选了，直接返回0

        int &res = memo[i][j];

        if (res != -1) return res; // 如果当前状态被计算过了，将计算结果返回给上一层

        res = dfs(dfs, i-1, j); // 不选额第i个物品，直接递归到第i-1个物品

        if (j >= v[i]) { // 说明可以选择第i个物品，背包能放得下

            res = max(res, dfs(dfs, i-1, j-v[i]) + w[i]); // 选择第 i 个物品，递归到第 i-1 个物品
        }

        return memo[i][j] = res; // 保存当前的状态
    };
    cout << dfs(dfs, n, m) << endl; // 递归入口，从第n间物品选，初始背包容量为m
}