#include <cstdio>

using namespace std;
int n,g,gr,pr,i,p[1010],sol,j;
int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;i++)p[i]=-1;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&gr,&pr);
        if(pr>=g)
        {
            sol=pr;
            continue;
        }
        for(j=g-gr;j<g;j++)
            sol=sol<p[j]+pr?sol:p[j]+pr;
        for(j=g;j>=gr;j--)
            p[j]=p[j]<p[j-gr]+pr?p[j]:p[j]-gr+pr;
    }
    printf("%d",sol);
    return 0;
}