//energii
#include<bits/stdc++.h>
#define debug cerr<<"ok";
#define oo (1<<30)
#define MAXN 10001
using namespace std;

int n,i,j,w,D[MAXN][MAXN/2];

int main ()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    scanf("%d%d",&n,&w);  // nr generatoare, W necesara
    int  e, c;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=w;j++)
            D[i][j]=oo;
    for(i=1;i<=n;i++){
        scanf("%d%d",&e,&c);
        for(j=w;j>=1;j--){
            if( j <= e)
                D[i][j] = min(D[i-1][j],c);
            else
                D[i][j] = min(D[i-1][j],D[i-1][j-e]+c);
        }
    }
    if(D[n][w] == oo)
        printf("1");
    else
    printf("%d",D[n][w]);

    return 0;
}