#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

typedef map< int, int, less<int> > jar_map;

struct jar{
  int weight;
  int yum;
};

void set_grid(vector<jar> jars,int weight, int n);

bool check(struct jar A,struct jar B) 
{
  if(A.weight == B.weight) return (A.yum<B.yum);
  return (A.weight<B.weight);
}

int main()
{
  int i,weight,n,nweight,yumminess;

  vector<jar> jars;

  while(1)
    {
      cin >> weight >> n;

      if(weight==0 && n==0) break;

      jars.resize(n);

      for(i=0;i<n;i++)
	{
	  //jars[i] = new jar;
	  cin >> nweight >> yumminess;
	  jars[i].weight = nweight;
	  jars[i].yum = yumminess;
	}

      sort(jars.begin(),jars.end(),check);

      set_grid(jars,weight,n);

      jars.clear();
    }

  return(0);
}

void set_grid(vector<jar> jars,int weight, int n)
{
  int max[weight+1][n+1];
  int i,j;

  vector<vector<vector<int> > > path;

  path.resize(weight+1);

  for(i=0;i<=weight;i++) path[i].resize(n+1);

  for(i=0;i<=weight;i++)
    {
      for(j=0;j<=n;j++)
	{
	  if(i==0||j==0) max[i][j]=0;
	  else if(jars[j-1].weight > i) 
	    {
	      max[i][j] = max[i][j-1];
	      path[i][j] = path[i][j-1];
	    }
	  else if(max[i][j-1] >= jars[j-1].yum + max[i-jars[j-1].weight][j-1])
	    {
	      max[i][j] = max[i][j-1];
	      path[i][j] = path[i][j-1];
	    }
	  else if(max[i][j-1] < jars[j-1].yum + max[i-jars[j-1].weight][j-1])
	    {
	      max[i][j] = jars[j-1].yum + max[i-jars[j-1].weight][j-1];
	      path[i][j] = path[i-jars[j-1].weight][j-1];
	      path[i][j].push_back(j-1);
	    }
	}
    }

  cout<<max[weight][n]<<endl;
  for(i=0;i<path[weight][n].size();i++) cout<<jars[path[weight][n][i]].weight
					    <<' '
					    <<jars[path[weight][n][i]].yum
					    <<endl;
}