#include <bits/stdc++.h>
using namespace std;

class Rucsac {
	int n, greutate;
	vector <int> w;
	vector <int> p;
public:
	void read_data() {
	    ifstream fin("rucsac.in");

	    /* read the capacity of the bag
	    and the number of objects
	    */
	    fin >> n >> greutate;
	    for (int i = 0, weight, price; i < n; i++) {
	    	fin >> weight >> price;
	    	w.push_back(weight);
	    	p.push_back(price);
	    }
	}
	int dp_bag() {
		int cost[n+1][greutate+1];
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= greutate; j++) {
				cost[i][j] = 0;
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= greutate; j++) {
				if (j < w[i-1])
					cost[i][j] = cost[i-1][j];
				if (j == w[i-1])
					cost[i][j] = p[i-1];
				if (j > w[i-1])
					cost[i][j] = max(cost[i-1][j], p[i-1] + cost[i-1][j - w[i-1]]);

			}
		}
		return cost[n][greutate];
	}
    void print_output(int result) {
    	ofstream fout("rucsac.out");
    	fout << result;
    	fout.close();
	}
	void solve_task() {
		read_data();
		print_output(dp_bag());
	}

};

/* please keep main function clean :)))
*/
int main() {
	Rucsac *bag = new Rucsac();
	bag->solve_task();
	delete bag;
}