#include <fstream>
using namespace std;

ifstream cin("fin.txt");
ofstream cout("fout.txt");

int n, maxG, w[1001], p[1001];
int memo[10001][1001];

void read() {
    cin >> n >> maxG;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> p[i];
}

int maxProfit(int index, int remaining) {
    if (memo [index][remaining] != -1) return memo[index][remaining];
    int result;
    if (index == 0 || remaining == 0)
        result = 0;
    else if (w[index] > remaining)
        result = maxProfit(index - 1, remaining);
    else {
        int notIncluding = maxProfit(index - 1, remaining);
        int including = p[index] + maxProfit(index - 1, remaining - w[index]);
        result = max(notIncluding, including);
    }
    memo[index][remaining] = result;
    return result;
}

int main()
{
    memset(memo, -1, sizeof(memo));
    read();
    cout << maxProfit(n, maxG);
}