#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main() {
	int n,g, w_max = 0;
	fin>>n>>g;
	vector<pair<int,int>> rucsac(n+5);
	for (int i = 1; i <=n; i++) {
		fin>>rucsac[i].first>>rucsac[i].second;
		w_max+=rucsac[i].first;
	}
	int sol[w_max+1000];
	int rezultat = -1;
	for (int i = 1; i <= w_max; i++)
		sol[i] = -1;
	sol[0] = 0;
	for (int k = 1; k <= n; k++) {
		for (int i = w_max; i >= 0; i--) {
			if(sol[i] != -1) {
				if (sol[i] + rucsac[k].second > sol[i+rucsac[k].first]) {
					sol[i+rucsac[k].first] = sol[i] + rucsac[k].second;
					if (sol[i+rucsac[k].first] > rezultat)
						rezultat = sol[i+rucsac[k].first];
				}
			}
		}
	}
	cout<<rezultat;
}