#include <cstdlib>
#include <cstdio>

using namespace std;

int d[10001];

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

   int n,G,g,p,smax,i,j;

   scanf("%d%d",&n,&G);

   for(i=1;i<=G;i++)
   d[i]=-1;

   smax=0;

   for(i=1;i<=n;i++)
   {
       scanf("%d%d",&g,&p);
       for(j=smax;j>=0;j--)
       if(d[j]!=-1 && j+g<=G)
       {
           if(d[j+g]<d[j]+p)
           d[j+g]=d[j]+p;

           if(j+g>smax)
           smax=j+g;

       }

   }

for(i=1;i<=G;i++)
printf("%d ",d[i]);

int profit=0;

for(i=G;i>=1;i--)
if(d[i]>profit)
profit=d[i];

printf("%d",profit);

    return 0;
}