#include<stdio.h>
int i,j,n,g,c[5005],gr[5005],l1[10004],l2[10004];
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&gr[i],&c[i]);
    }
    for(i=1;i<=g;i++)
    {

        if(i>=gr[1])
            l1[i]+=c[1];

    }

    for(i=2;i<=n;i++)
    {

        for(j=1;j<=g;j++)
            if(j>=gr[i])
            {
                if(l1[j]>c[i]+l1[j-gr[i]])
                    l2[j]=l1[j];
                else
                {


                    l2[j]=c[i]+l1[j-gr[i]];
                }

            }
            else
                l2[j]=l1[j];
        for(j=1;j<=g;j++)
            l1[j]=l2[j];

    }
    printf("%d",l1[g]);
    return 0;
}