#include <fstream> #define NMAX 5004
#define GMAX 10002
using namespace std; ifstream fin("rucsac.in"); ofstream fout("rucsac.out"); int n, G, g[NMAX], c[NMAX], cmax[GMAX]; void citire(); void pd();int main(){ citire(); pd(); fout << cmax[G] << '\n'; return 0;}void citire(){int i;fin >> n >> G;for (i = 1; i <= n; i++) fin >> g[i] >> c[i];}void pd(){int i, x; cmax[0] = 0;for (i = 1; i <= n; i++) for (x = G; x > 0; x--) if (x >= g[i]) if (cmax[x] < c[i] + cmax[x - g[i]]) cmax[x] = c[i] + cmax[x - g[i]];}