#include<cstdio>
#include <algorithm>
#define GMAX 10002
using namespace std;
struct obiect {int g,c;} a[20];
int n,i,j,line,G,d[2][GMAX];
int main()
{
 freopen("rucsac.in","rt",stdin);
 freopen("rucsac.out","wt",stdout);
 scanf("%d%d",&n,&G);
 for(i=1;i<=n;++i) scanf("%d%d",&a[i].g,&a[i].c);
 for(i=1;i<=n;i++,line=1-line)
	for(int j=0;j<=G;j++)
		{
		 d[1-line][j]=d[line][j];
		 if(a[i].g<=j) d[1-line][j] = max(d[1-line][j], d[line][j - a[i].g] + a[i].c); 
		}
 printf("%d\n",d[line][G]);
 return 0;
}