#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

int solution (int W, const int w[], const int p[], int size) {

    int i, j;
    int m[2][W + 1];

    for (j = 0; j <= W; ++j) {
        m[0][j] = 0;
    }

    for (i = 1; i <= size; ++i) {
        for (j = 0; j <= W; ++j) {
            m[1][j] = m[0][j];
            if (w[i - 1] <= j) {
                m[1][j] = std::max(m[1][j], m[0][j - w[i - 1]] + p[i - 1]);
            }
        }
        for (j = 0; j <= W && i != size; ++j) {
            m[0][j] = m[1][j];
        }
    }

    return m[1][W];

}

int main() {

    std::ifstream in;
    std::ofstream out;
    in.open("rucsac.in");
    out.open("rucsac.out");

    int size, W;
    in >> size >> W;
    int wt[size], val[size];
    for (int i = 0; i < size; ++i) {
        in >> wt[i] >> val[i];
    }
    out << solution(W, wt, val, size);

    in.close();
    out.close();

    return 0;

}