#include <stdio.h>

using namespace std;
FILE *f,*g;
int a[1002][5002],ng,gr;
struct
{
    int c,g;
}v[1001];
void read()
{
    fscanf(f,"%d %d",&ng,&gr);
    for(int i=1;i<=ng;i++)
        fscanf(f,"%d %d",&v[i].g,&v[i].c);
}
void dinamica()
{
    int i,j;
    for(i=0;i<=ng;i++)
        for(j=1;j<=gr;j++)
            a[i][j]=999999;
    for(i=1;i<=ng;i++)
        for(j=1;j<=gr;j++)
            if(v[i].g<=j)
                if(v[i].c+a[i-1][j-v[i].g]<a[i-1][j])
                    a[i][j]=v[i].c+a[i-1][j-v[i].g];
                else
                    a[i][j]=a[i-1][j];
            else
                a[i][j]=a[i-1][j];

}
int main()
{
    f=fopen("energii.in","r");
    g=fopen("energii.out","w");
    read();
    dinamica();
    fprintf(g,"%d",a[ng][gr]);
    return 0;
}