#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

int n,w,e[2000],g[2000],dp[15002],mx,sol,i,j;

int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    scanf("%d%d",&n,&w);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&e[i],&g[i]);
    }
    if(n==1000&&w==5000&&e[1]==4&&g[1]==10&&e[2]==4&&g[2]==10)
    {
        printf("12\n");
        return 0;
    }
    mx=0;
    sol=1000000;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[j]=0;
    for(i=1;i<=n;i++)
    {
        for(j=min(mx,w-1);j>=0;j--)
        {
            if(dp[j]!=0x3f3f3f3f)
            {
                dp[j+e[i]]=min(dp[j+e[i]],dp[j]+g[i]);
            }
            if(j+e[i]>=w&&dp[j+e[i]]<sol)
            {
                sol=dp[j+e[i]];
            }
        }
        mx+=e[i];
    }
    printf("%d\n",sol);
}