#include<stdio.h>
int cost[1001][5001],pret[1001],v[1001];
int main()
{
    FILE *fin,*fout;
    fin=fopen("energii.in","r");
    fout=fopen("energii.out","w");
    int n,sum;
    fscanf(fin,"%d%d",&n,&sum);
    int i;
    for(i=1; i<=n; i++)
        fscanf(fin,"%d%d",&v[i],&pret[i]);
    for(i=0; i<=sum; i++)
        cost[0][i]=999999999;
    for(i=0; i<=n; i++)
        cost[i][0]=999999999;
    for(i=1; i<=n; i++)
    {
        int j;
        for(j=1; j<=sum; j++)
        {
            if(v[i]>=j)
            {
                if(cost[i-1][j]>pret[i])
                {
                    cost[i][j]=pret[i];
                }
                else
                {
                    cost[i][j]=cost[i-1][j];
                }
            }
            else
            {
                if(cost[i-1][j]<cost[i-1][j-v[i]]+pret[i])
                    cost[i][j]=cost[i-1][j];
                else
                    cost[i][j]=cost[i-1][j-v[i]]+pret[i];
            }
        }
    }
    fprintf(fout,"%d",cost[n][sum]);
    return 0;
}