#include<cstdio>
int v[1001],p[1001],g[1001];



int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int n,w,i,j;
    scanf("%d%d",&n,&w);
    for(i=1;i<=n;++i)
        scanf("%d%d",&g[i],&p[i]);
    for(i=1;i<=n;++i)
        for(j=w;j>=1;--j)
            if(v[j]+p[i]<v[i+g[i]])
                v[i+g[i]]=v[j]+p[i];
    printf("%d",v[w]);
    return 0;
}