#include <stdio.h>

using namespace std;

FILE *f=fopen("energii.in","r");
FILE *g=fopen("energii.out","w");

int i,j,G,W,EG[1000],CG[1000],st[5000];

int main()
{
    fscanf(f,"%d%d",&G,&W);
    for(i=1;i<=G;i++)
     fscanf(f,"%d%d",&EG[i],&CG[i]);
    for(i=1;i<=W;i++)
    {
        st[i]=999;
        for(j=1;j<=G;j++)
         if(st[i-EG[j]]+CG[j]<st[i])
          st[i]=st[i-EG[j]]+CG[j];
    }
    return 0;
}