#include <fstream>

using namespace std;

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

// 1 ≤ N ≤ 5000
// 1 ≤ G ≤ 10000
// 0 ≤ Wi, Pi ≤ 10000

const int MAX_N = 5005;
const int MAX_G = 10005; 

struct t_obiect {
    int weight;
    int val;
};

int dp[2][MAX_G];

int main() {

    int nr_elem;
    int weight;
    t_obiect objects[MAX_N];

    fin >> nr_elem >> weight;

    for (int i = 1; i <= nr_elem; i++) {
        int weight;
        int val;

        fin >> weight;
        fin >> val;

        t_obiect ob = {weight, val};
        objects[i] = ob;
    }

    for (int i = 1; i <= nr_elem; i++) {
        for (int w = 0; w <= weight; w++) {
            if (objects[i].weight > w) {
                dp[1][w] = dp[0][w];
            } else {
                int without_object = dp[0][w];
                int with_object = dp[0][w - objects[i].weight] + objects[i].val;

                dp[1][w] = max(without_object, with_object);
            }
        }

        for (int w = 0; w <= weight; w++) {
            dp[0][w] = dp[1][w];
        }
    }

    fout << dp[1][weight];

    return 0;
}