#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g;
int w,p;
int i,j,lc,lp;
int c[2][10001];

//w=weight
//p=price
int main()
{
    fi>>n>>g;

for (i = 1,lc = 1,lp = 0 ;  i<= n ; swap(lc,lp),i++ )
{fi>> w>> p;
        for (j = 0; j <= g; ++j )
		  { c[lc][j] = c[lp][j];
			if ( j >= w && c[lc][j] < c[lp][j - w] + p )
				           c[lc][j] = c[lp][j - w] + p;
		  }

}

fo<<c[lp][g];
    return 0;
}