#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
int n, w;
int weight[101];
int value[101];
ll memo[101][100001];
ll knapsack(int at, int weight_left) {
    if(at == n or weight_left == 0) {
        return 0;
    }
    if(memo[at][weight_left] != -1) {
        return memo[at][weight_left];
    }
    ll result = 0;
        result = max(result, knapsack(at + 1, weight_left));

        if(weight_left - weight[at] >= 0) {
            result = max(result, knapsack(at + 1, weight_left - weight[at]) + value[at]);
        }
    return memo[at][weight_left] = result;
}
int main() {
    cin >> n >> w;
    for(int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= w; j++) {
            memo[i][j] = -1;
        }
    }
    cout << knapsack(0, w) << endl;
    return 0;
}
/*
 3 8

 3 30
 4 50
 5 60
 knapsack(0, 8) --> max(knapsack(1, 8), knapsack(1, 8 - 3) + 30)
 knapsack(1, 8) --> max(knapsack(2, 8), knapsack(2, 4) + 50)
 knapsack(2, 8) --> max(knapsack(3, 8), knapsack(3, 3) + 60)
 knapsack(3, 8) = 0
 knapsack(3, 3) = 0

 **/