#include<cstdio>
using namespace std;
struct andreea{
    int e,c;
};
andreea v[5001];
int i,g,w,j,s,min,maxi;
int a[1001][15001];
int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    scanf("%d %d",&g,&w);
    maxi=0;
    s=0;
    for(i=1;i<=g;i++)
    {
        scanf("%d %d",&v[i].e,&v[i].c);
        if(v[i].e>maxi)
            maxi=v[i].e;
        s=s+v[i].e;
    }
    a[1][v[1].e]=v[1].c;
    for(j=1;j<=w+maxi;j++)
    {
        if(j!=v[1].e)
            a[1][j]=20;

    }

    for(i=2;i<=g;i++)
    {
        a[i][1]=20;
            }
    for(i=2;i<=g;i++)
        for(j=2;j<=w+maxi;j++)
            if(j>=v[i].e)
            {
                if(a[i-1][j]>a[i-1][j-v[i].e]+v[i].c)
                    a[i][j]=a[i-1][j-v[i].e]+v[i].c;
                else
                    if(a[i-1][j]<a[i-1][j-v[i].e]+v[i].c)
                        a[i][j]=a[i-1][j];

            }
            else
                a[i][j]=a[i-1][j];
    for(j=w;j<=w+maxi;j++)
        if(a[g][j]!=20)
        {
            printf("%d\n",a[g][j]);
            break;
        }

    return 0;
}