#include <iostream>
#include<fstream>

using namespace std;
ifstream in("rucsac.in");

void cpy(int n,int *aktual,int *regi)
{
    for(int i=0;i<n;i++)
    {

      regi[i]=aktual[i];
    }
}
int main()
{
  //beolvas
  int n,g,suly,penz;
  in>>n>>g;
  int sulyt[n+1],ar[n+1];
  int aktualis[g+1]={0},regi[g+1]={0};
  int van[n+1]={0};
  for(int i=1;i<=n;i++)
  {
      in>>suly>>penz;
      sulyt[i]=suly;
      ar[i]=penz;
      if(aktualis[suly]<penz)
      {
          aktualis[suly]=penz;
        van[suly]=1;
      }

      for(int j=1;j<g;j++)
      {

          if(regi[j]!=0&&penz+regi[j]>regi[suly+j])
          {
              aktualis[suly+j]=penz+regi[j];
              //van[i+j]=1;

          }
      }
          cout<<suly<<"::"<<penz<<endl;
          cout<<"r"<<endl;
            for(int i=1;i<=g;i++)
              {
                  cout<<regi[i]<<" ";
              }
              cout<<endl;
              cout<<"a"<<endl;
               for(int i=1;i<=g;i++)
              {
                  cout<<aktualis[i]<<" ";
              }
              cout<<endl;


       cpy(g,aktualis,regi);

  }

    return 0;
}