record

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100 + 7;
int n,m;
bool a[MAXN][MAXN];
int dp[MAXN][MAXN],ans;
int sqr(int x) {return x*x;} 
bool inarea(int xb,int yb,int x0,int y0)
{
	if (yb%2==1) return x0 >= xb && y0 >= yb && y0 <= yb+(x0-xb)*2;
	return x0 <= xb && y0 <= yb && y0 >= yb - (xb-x0)*2;
}
int lmt(int xb,int yb,int x0,int y0)
{
	int l=1,r=n,md,ans=1;
	while (l<=r)
	{
		md = (l+r)>>1;
		if ((y0%2==1&&(inarea(xb,yb,x0+md-1,y0)||inarea(xb,yb,x0+md-1,y0+2*(md-1))))||
			(y0%2==1&&(inarea(xb,yb,x0-md+1,y0)||inarea(xb,yb,x0-md+1,y0-2*(md-1))))) r = md-1;
		else ans = md,l = md+1;
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		a[x][y] = 1;
	}
	for (int i=n;i>=1;i--)
		for (int j=1;j<=i*2-1;j+=2)
		{
			if (a[i][j]==1) continue;
			dp[i][j] = 1;
			if (a[i+1][j+1]==1) continue;
			dp[i][j] = 1 + min(dp[i+1][j],dp[i+1][j+2]);
		}
	for (int i=1;i<=n;i++)
		for (int j=2;j<=i*2-1;j+=2)
		{
			if (a[i][j]==1) continue;
			dp[i][j] = 1;
			if (a[i-1][j-1]==1) continue;
			dp[i][j] = 1 + min(dp[i-1][j],dp[i-1][j+2]);
		}
	for (int x1=1;x1<=n;x1++)
		for (int y1=1;y1<=x1*2-1;y1++)		
			for (int x2=x1;x2<=n;x2++)
				for (int y2=((x2==x1)?y1+1:1);y2<=x2*2-1;y2++)
				{
					if (a[x1][y1]||a[x2][y2]) continue ;
					if (y1%2==0&&y2%2==1) ans = max(ans,sqr(dp[x1][y1]) + sqr(dp[x2][y2]));
					else if (y1%2==1&&y2%2==0) 
					{
						if (inarea(x1,y1,x2,y2)) 
						{
							int sum = x2 - x1 + 1,lm1 = dp[x1][y1],lm2 = dp[x2][y2];
							if (lm1>=sum) lm1 = sum - 1;
							if (lm2>=sum) lm2 = sum - 1;
							ans = max(ans,max(sqr(lm1)+sqr(min(sum-lm1,lm2)),sqr(lm2)+sqr(min(sum-lm2,lm1))) );
						}
						else ans = max(ans,sqr(dp[x1][y1]) + sqr(dp[x2][y2]));
					}
					else if (x1%2 == x2%2)
					{
						if (inarea(x1,y1,x2,y2))
						{
							if (x1%2==1) ans = max(ans,sqr(dp[x2][y2])+sqr(min(x2-x1,dp[x1][y1])));
							else ans = max(ans,sqr(dp[x1][y1])+sqr(min(x2-x1,dp[x2][y2])));
						}
						else
						{
							int t = max( sqr(min(dp[x2][y2],lmt(x1,y1,x2,y2))) + sqr(dp[x1][y1]) ,sqr(min(dp[x1][y1],lmt(x2,y2,x1,y1)))+sqr(dp[x2][y2]));
							ans = max(ans ,  t);
						}
					}
				}
	printf("%d",ans);
	return 0;
}