#include<fstream>
#include<iostream>

using namespace std;
int profit[1001];
int weight[1001];
int objects, maxweight;

void read() {
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in >> objects >> maxweight;
    for (int i = 0; i < objects; i++) {
        in >> weight[i] >> profit[i];

    }


}

int DP() {
    int maxvalue[objects + 1][maxweight + 1];//the biggest value at the x weight formed from first n objects;
    int remains = 0;
    for (int n = 0; n <= objects; n++) {
        for (int x = 0; x <= maxweight; x++) {
            if (n == 0) {
                maxvalue[n][x] = 0;
            } else {
                if (weight[n-1] <= x) {
                    remains = x - weight[n-1];
                    maxvalue[n][x] = std::max(maxvalue[n-1][x], maxvalue[n - 1][remains] + profit[n-1]);

                } else {
                    maxvalue[n][x] = maxvalue[n - 1][x];

                }
            }

        }
    }
    
}

int main() {

read();
out<<DP();
return 0;

}