//这是一道完全背包。与0/1背包不同，空间优化后不必逆序，
//以实现多次选取。
//此外本题要求装满，所以f[j](j!=0)初始化为负无限大。
//关于“装满”，参见jake1036的《01背包问题总结（一）》。
#include <stdio.h>
#include <limits.h>
int main()
{
	long int n,m,p[10001],v[10002],f[10001];
	scanf("%ld%ld",&n,&m);
	int i,j;
	for(i=1;i<=n;i++) scanf("%ld%ld",&p[i],&v[i]);
	for(j=1;j<=m;j++) f[j]=LONG_MIN;
	for(i=1;i<=n;i++)
		for(j=p[i];j<=m;j++)
			if(f[j-p[i]]+v[i]>f[j]) f[j]=f[j-p[i]]+v[i];
	printf("%ld",f[m]);
	return 0;
}