/*
    Keep It Simple!
*/

#include <stdio.h>

#define max(a,b) a > b ? a : b

int n,C,v[5001],w[5001],M[10001];

int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	
	scanf("%d %d",&n,&C);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&w[i],&v[i]);
	
	for(int i=n;i>=1;i--)
	    for(int j=C;j>=1;j--)
	    {
			if(w[i] > j )
				M[j] = M[j];
			else
				M[j] = max(M[j],M[j-w[i]]+v[i]);
	    }
		
	printf("%d",M[C]);
}