#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct val
{
    int e,c;
}val;
val v[1001];
int s[1001][5001];

int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int n,w,i,j,sol=2000000000;
    scanf("%d%d",&n,&w);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].e,&v[i].c);

    for(i=0;i<=n;i++)
        for(j=0;j<w;j++)
            s[i][j]=1000000000;
    s[0][0]=0;


    for(i=1;i<=n;i++)
    {
        for(j=0;j<w;j++)
        {
            if(j+v[i].e>=w)
            {
                if(s[i-1][j]+v[i].c<sol)
                    sol=s[i-1][j]+v[i].c;
            }
            else
                s[i][j]=min(s[i-1][j],s[i-1][j-v[i].e]+v[i].c);
        }
    }
    printf("%d\n",sol);
    return 0;
}