#include <fstream>

using namespace std;

const int DIM = 5010;
const int MAX_WEIGHT = 10010;

struct Item {
    int w, p;
};

Item items[DIM];
int dp[2][MAX_WEIGHT];

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

    int n, wMax;
    fin >> n >> wMax;
    for (int i = 1; i <= n; i++)
        fin >> items[i].w >> items[i].p;

    int line = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = wMax; j >= 0; j--) {
            dp[line][j] = dp[1 - line][j];
            if (j - items[i].w >= 0 && dp[line][j] < dp[1 - line][j - items[i].w] + items[i].p)
                dp[line][j] = dp[1 - line][j - items[i].w] + items[i].p;
        }

        line = 1 - line;
    }

    int bestProfit = 0;
    for (int i = 0; i <= wMax; i++)
        bestProfit = max(bestProfit, dp[1 - line][i]);

    fout << bestProfit;

    fin.close();
    fout.close();
    return 0;
}