#include <stdio.h>
#define NMAX 5002

long int n,w,i,j,old[NMAX],nou[NMAX],cst[NMAX],ew[NMAX];


void citire()
{
freopen("energii.in","r",stdin);
freopen("energii.out","w",stdout);
scanf("%ld\n%ld",&n,&w);
for (i=1;i<=n;i++)
        scanf("%ld %ld",&ew[i],&cst[i]);
}


void solve()
{
old[0]=0;
for (i=1;i<=w;i++)
        old[i]=-1;
for (i=1;i<=n;i++)
        {

        for (j=1;j<=w;j++)
                {
                if (j-ew[i]<=0) nou[j]=cst[i];
                        else if (old[j-ew[i]]==-1) nou[j]=old[j];
                                else nou[j]=old[j-ew[i]]+cst[i];
                if (old[j]==-1) continue;
                        else if (old[j]<nou[j]) nou[j]=old[j];                
                }

        for (j=0;j<=w;j++)
                old[j]=nou[j];
        }
printf("%ld",nou[w]);
}

int main()
{
citire();
solve();
return 0;
}