#include<stdio.h>
struct intz
{
    int c,e;
};
intz gen[1024];
int a[1024][5024];
int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int n,s,i,j;
    scanf("%d%d",&n,&s);
    for(i=1;i<=n;i++)
        scanf("%d%d",&gen[i].e,&gen[i].c);
    for(i=1;i<=n;i++)
        for(j=1;j<=s;j++)
            if(j-gen[i].e==0)
            {
                a[i][j]=gen[i].c;
                if(a[i-1][j]<a[i][j] && a[i-1][j])
                    a[i][j]=a[i-1][j];
            }
            else
            {
                if(a[i-1][j]!=0)
                    a[i][j]=a[i-1][j];
                if(j-gen[i].e>0 && a[i-1][j-gen[i].c] && a[i-1][j-gen[i].c]+gen[i].c<a[i][j])
                    a[i][j]=a[i-1][j-gen[i].c]+gen[i].c;
            }
    printf("%d",a[n][s]);
    return 0;
}