// orchard folds mjd@cs.auckland.ac.nz
// 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

bool inBox(int x1, int y1, int x2, int y2, int x, int y)
{
    if (x < x1 || x > x2) return false;
    if (y < y1 || y > y2) return false;
    return true;
}

bool fold3(const vector<int> &x3, const vector<int> &y3, int len)
{
    for (int i=0; i<x3.size(); i++)
    {  
      if (!inBox(0,0,len,len,x3[i],y3[i])) return false;
    }
    return true;
}
// lower left corner
bool fold2a(const vector<int> &x2, const vector<int> &y2, int len)
{
    assert(x2.size());
    vector<int> x3, y3;
    int i; for (i=0; i<x2.size(); i++)
    {
       if (!inBox(0,0,len,len,x2[i],y2[i]))
       { x3.push_back(x2[i]); y3.push_back(y2[i]); }
    }
    if (x3.size()==0) return true;
    int minx = *min_element(x3.begin(),x3.end());
    int miny = *min_element(y3.begin(),y3.end());
    for (i=0; i<x3.size(); i++) { x3[i] -= minx; y3[i] -= miny; }

    if (fold3(x3,y3,len)) return true;
    return false;
}
// upper left corner
bool fold2b(const vector<int> &x2, const vector<int> &y2, int len)
{
    assert(x2.size());
    int maxy = *max_element(y2.begin(),y2.end());
    
    vector<int> x3, y3;
    int i; for (i=0; i<x2.size(); i++)
    {
       if (!inBox(0,maxy-len,len,maxy,x2[i],y2[i]))
       { 
  	x3.push_back(x2[i]); y3.push_back(y2[i]); 
       }
    }
    if (x3.size()==0) return true;
    int minx = *min_element(x3.begin(),x3.end());
    int miny = *min_element(y3.begin(),y3.end());
    for (i=0; i<x3.size(); i++) { x3[i] -= minx; y3[i] -= miny; }

    if (fold3(x3,y3,len)) return true;
    return false;
}
// lower left corner
bool fold1a(const vector<int> &x, const vector<int> &y, int len)
{
    vector<int> x2, y2;
    int i; for (i=0; i<x.size(); i++)
    {
	    if (!inBox(0,0,len,len,x[i],y[i]))
	    { x2.push_back(x[i]); y2.push_back(y[i]); }
    }
    if (x2.size()==0) return true;
    int minx = *min_element(x2.begin(),x2.end());
    int miny = *min_element(y2.begin(),y2.end());
    for (i=0; i<x2.size(); i++) { x2[i] -= minx; y2[i] -= miny; }

    if (fold2a(x2,y2,len) ||
	fold2b(x2,y2,len)) return true;
    return false;
}
// lower right corner
bool fold1b(const vector<int> &x, const vector<int> &y, int len, int maxx)
{
    vector<int> x2, y2;
    int i; for (i=0; i<x.size(); i++)
    {
	    if (!inBox(maxx-len,0,maxx,len,x[i],y[i]))
	    { x2.push_back(x[i]); y2.push_back(y[i]); }
    }
    if (x2.size()==0) return true;
    int minx = *min_element(x2.begin(),x2.end());
    int miny = *min_element(y2.begin(),y2.end());
    for (i=0; i<x2.size(); i++) { x2[i] -= minx; y2[i] -= miny; }

    if (fold2a(x2,y2,len) ||
	fold2b(x2,y2,len)) return true;
    return false;
}
// upper left corner
bool fold1c(const vector<int> &x, const vector<int> &y, int len, int maxy)
{
    vector<int> x2, y2;
    int i; for (i=0; i<x.size(); i++)
    {
	    if (!inBox(0,maxy-len,len,maxy,x[i],y[i]))
	    { x2.push_back(x[i]); y2.push_back(y[i]); }
    }
    if (x2.size()==0) return true;
    int minx = *min_element(x2.begin(),x2.end());
    int miny = *min_element(y2.begin(),y2.end());
    for (i=0; i<x2.size(); i++) { x2[i] -= minx; y2[i] -= miny; }

    if (fold2a(x2,y2,len) ||
	fold2b(x2,y2,len)) return true;
    return false;
}
// upper right corner
bool fold1d(const vector<int> &x, const vector<int> &y, int len, int maxx, int maxy)
{
    vector<int> x2, y2;
    int i; for (i=0; i<x.size(); i++)
    {
	    if (!inBox(maxx-len,maxy-len,maxx,maxy,x[i],y[i]))
	    { x2.push_back(x[i]); y2.push_back(y[i]); }
    }
    if (x2.size()==0) return true;
    int minx = *min_element(x2.begin(),x2.end());
    int miny = *min_element(y2.begin(),y2.end());
    for (i=0; i<x2.size(); i++) { x2[i] -= minx; y2[i] -= miny; }

    if (fold2a(x2,y2,len) ||
	fold2b(x2,y2,len)) return true;
    return false;
}

int main(int argc, char* argv[])
{
    int s, n;

    while (true)
    {
      cin >> s >> n;
      if (s==0 && n==0) break;

      vector<int> x(n), y(n);

      int i; for (i=0; i<n; i++)  cin >> x[i] >>  y[i];

      if (n<=3)  // trivial zero length boxes
      { 
	 cout << s << ' ' << 0 << endl;
	 continue;
      }

      int minx = *min_element(x.begin(),x.end());
      int miny = *min_element(y.begin(),y.end());

      for (i=0; i<n; i++) { x[i] -= minx; y[i] -= miny; }

      int maxx = *max_element(x.begin(),x.end());
      int maxy = *max_element(y.begin(),y.end());

      int lbound = 0, ubound = max(maxx,maxy);

      while (lbound < ubound)
      {
	int mid = (lbound+ubound)/2;

	if (fold1a(x,y,mid) ||
            fold1b(x,y,mid,maxx) ||
            fold1c(x,y,mid,maxy) ||
            fold1d(x,y,mid,maxx,maxy)) { ubound = mid; }
	else { lbound=mid+1; }
      }

      cout << s << ' ' << lbound << endl;
    }
}