#include <fstream>
#include <iostream>
#include <iomanip>

using namespace std;

struct obiect {
	int g, p;
};

obiect a[20];
int n, G, l, g, p, c, pn, mp[20][20];
ifstream f ("rucsac.in");

int main() {
	f >> n >> G;
	for (l = 1; l <= n; l++)
		f >> a[l].g >> a[l].p;
	f.close();
	for (l = 1; l <= n; l++) {
    for (c = 1; c <= G; c++) {
      if (a[l].g <= c) { // Obiectul curent incape in rucsac?
        pn = a[l].p+mp[l-1][c-a[l].g];
        if (pn > mp[l-1][c])
          mp[l][c] = pn;
        else
          mp[l][c] = mp[l-1][c];
      }
      else
        mp[l][c] = mp[l-1][c];
      //cout << setw(4) << mp[l][c];
    }
    //cout << endl;
	}
	cout << mp[n][G];
	return 0;
}