#include<stdio.h>
#define max(x,y) ((x)>(y)?1:0)
int m[3][10001],n,G;
void bord(){
	int j;
	for(j=1;j<=G;j++){
		m[1][j]=0;
	}
}
void schimb(){
	int j;
	for(j=1;j<=G;j++){
		m[1][j]=m[2][j];
	}
}
int main(){
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	int i,g,w,j;
	scanf("%d%d",&n,&G);
	bord();
	for(i=1;i<=n;i++){
		scanf("%d%d",&g,&w);
		for(j=1;j<=G;j++){
			if(j<g){
				m[2][j]=m[1][j];
			}
			else{
				if(m[1][j]>m[1][j-g]+w){
					m[2][j]=m[1][j];
				}
				if(m[1][j]<=m[1][j-g]+w){
					m[2][j]=m[1][j-g]+w;
				}
			}
		}
		schimb();
	}
	printf("%d\n",m[1][G]);
	return 0;
}