/* Yumminess

by Raymond Le Grand

*/

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct jar{
  int w;
  int y;
  int inside; //in knapsack?
};

bool jCompW(jar i, jar j){ return (i.w<j.w);}

bool jCompY(jar i, jar j){
  return ((i.y)<(j.y));
}

int main(){
  int wMax,nJars;
  int w,total;
  jar ajar;
  vector<jar> jlist;
  vector<vector<int> > tbl;

  while(true){
    
    cin>>wMax>>nJars;
    if((wMax==0)&&(nJars==0))break;

    for (int i=0;i<nJars;i++){
      //ajar=new jar;
      cin>>ajar.w>>ajar.y;
      ajar.inside=0;
      jlist.push_back(ajar);
    }
   
    //resize table
    tbl.resize(nJars+1);
    for (int i=0;i<nJars+1;i++){
      tbl[i].clear();
      tbl[i].resize(wMax+1);
    }
    //calculate table
    int j,w;
    for (j=1;j<=nJars;j++){
      for ( w=0;w<=wMax;w++){
      if (jlist[j-1].w>w){
	tbl[j][w]=tbl[j-1][w];
      }else{
	tbl[j][w]=max(tbl[j-1][w],jlist[j-1].y+tbl[j-1][w-jlist[j-1].w]);
      }
      }
    }
    //first part of answer:
    cout<<tbl[nJars][wMax]<<endl;

    /* table printout for debugging purposes
    for (int i=0;i<tbl.size();i++){
      for (int j=0;j<tbl[i].size();j++){
	cout<<tbl[i][j]<<' ';
      }
      cout<<endl;
    }
    */

    j=nJars;
    w=wMax;
    //now go back through array
    while ((j>0)&&(w>0)){
      if (tbl[j][w]!=tbl[j-1][w]){
	w=w-jlist[j-1].w;
	jlist[j-1].inside=1;
	j--;
      }else{
	j--;
      }
    }
    
    j=0;
    while(j<jlist.size()){
      if (jlist[j].inside==0){
	jlist.erase(jlist.begin()+j);
	j--;
      }
      j++;
    }
    stable_sort(jlist.begin(),jlist.end(),jCompY);
    stable_sort(jlist.begin(),jlist.end(),jCompW);
    
    //print out answer
    j=0;
    //while(jlist[j].inside==1){
    while(j<jlist.size()){
      cout<<jlist[j].w<<' '<<jlist[j].y<<endl;
      j++;
    }

    //clear answers for next round
    jlist.clear();
  
  }
  return 0;
}