#include<stdio.h>
#define maxg 5002
int g,w,i,j,a[maxg],x,y,c;
FILE *f,*d;
int main()
{f=fopen("energii.in","r");
d=fopen("energii.out","w");
fscanf(f,"%d %d",&g,&w);
for(i=1;i<=g;i++)
{fscanf(f,"%d %d",&x,&y);
if(y<a[x])
a[x]=y;}
for(i=1;i<=w;i++)
if(!a[i])
a[i]=maxg;
for(i=1;i<=w;i++)
for(j=i+1;j<=w;j++)
if(a[i]+a[j]<a[i+j])
a[i+j]=a[i]+a[j];
i=w;
while(!c)
{if(a[i]<maxg)
fprintf(d,"%d\n",a[i]);
c=1;}
fclose(f);
fclose(d);
return 0;}