#include <stdio.h>
#include <stdlib.h>
#define max(a,b) (a > b ? a : b)
#define min(a,b) (a < b? a : b)
#define MAX 10001
#define CAP_MAX 10001
#define INFINITE 1000000000
int n, W;
int energie[MAX], cost[MAX];
int v[2][MAX];
void readInput (){
int i;
FILE *f= fopen("energii.in","r");
fscanf(f,"%d%d", &n,&W);
for (i = 1; i <= n; i++)
fscanf(f,"%d%d", &energie[i],&cost[i]);
}
void run ()
{
int i, j, k;
FILE *g= fopen("energii.out","w");
for ( j=1; j<=W; j++)
v[0][j]=INFINITE;
for ( i = 1; i <= n; i++){
for ( j = 1; j <= W; j++){
v[1][j] = v[0][j];
if ( energie[i] <= j )
v[1][j]= min(v[1][j],v[0][j - energie[i]]+ cost[i]);
}
for ( k = 1; k <= W; k++)
v[0][k]=v[1][k];
}
fprintf(g,"%d", v[1][W]);
}
int main()
{
readInput();
run();
return 0;
}