#include<fstream.h>
long s[10005],eg[1005],cg[1005],g,w;
void cit()
{ifstream fin("energii.in");
  fin>>g>>w;
  long i;
   for(i=1;i<=g;++i)
	   fin>>eg[i]>>cg[i];
 fin.close();
}
void solve()
{s[0]=1;
 long i,j;
 for(i=1;i<=g;++i)
 { for(j=10005;j>=0;--j)
	 if(s[j]&&j+eg[i]<=10000)
	 {if(s[j+eg[i]]==0)
		 s[j+eg[i]]=s[j]+cg[i];
	   else
		   if(s[j+eg[i]]>s[j]+cg[i])
			   s[j+eg[i]]=s[j]+cg[i];
	 }
 }
}
void afis()
{ofstream fout("energii.out");
  long i;
   for(i=1;i<=10005;++i)
	   if(s[i])
		   fout<<i<<" "<<s[i]-1<<'\n';
 fout.close();
}
int main()
{cit();
 solve();
 afis();
 return 0;
}