#include <iostream>
#include <fstream>
#define dMAX 5001

using namespace std;

unsigned int n, capacity;
unsigned int matrix[dMAX][10001];

struct Element {
    unsigned int weight, profit;
} arr[dMAX];

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

unsigned int KnapSack(unsigned int m, unsigned int c) {
    unsigned int result;
    if (matrix[m][c] != 0) return matrix[m][c];
    if (m == 0 || c == 0) result = 0;
    else if (arr[m].weight > c) result = KnapSack(m - 1, c);
    else {
        unsigned int t1, t2;
        t1 = KnapSack(m - 1, c);
        t2 = arr[m].profit + KnapSack(m - 1, c - arr[m].weight);
        result = max(t1, t2);
    }
    matrix[m][c] = result;
    return result;
}

int main()
{
    unsigned int i, j;
    fin >> n >> capacity;
    for (i = 1; i <= n; i++) {
        fin >> arr[i].weight >> arr[i].profit;
    }
    fout << KnapSack(n, capacity);
    return 0;
}