#include <bits/stdc++.h>
using namespace std;

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

int n, w, dp[5010][10010];

struct rucsac{
    int profit;
    int weight;
}v[5010];

void knapsack() {
    for (int cap = 0; cap <= w; cap++)
        dp[0][cap] = 0;

    for (int i = 1; i <= n; i++)
        for (int cap = 0; cap <= w; cap++) {
            dp[i][cap] = dp[i - 1][cap];

            if (cap - v[i].weight >= 0) {
                int aux = dp[i - 1][cap - v[i].weight] + v[i].profit;
                dp[i][cap] = max(dp[i][cap], aux);
            }
        }

    out << dp[n][w];
    return;
}

int main(void) {
    in >> n >> w;
    for (int i = 1; i <= n; i++)
        in >> v[i].weight >> v[i].profit;

    knapsack();

    return 0;
}