#include"bits/stdc++.h"
using namespace std;
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;(a)<=i;i--)
#define R0F(i,a)ROF(i,0,a)
#define rep(a)F0R(_,a)
#define each(a,x)for(auto&a:x)
#define all(a)begin(a),end(a)
#define sz(x)int(size(x))
#define lla(x)rbegin(x),rend(x)
#define SUM(a)accumulate(all(a),0ll)
#define SUMM(a,b)accumulate(a,a+b,0ll)
#define MAX(a)(*max_element(all(a)))
#define MAXX(a,b)(*max_element(a,a+b))
#define MIN(a)(*min_element(all(a)))
#define MINN(a,b)(*min_element(a,a+b))
#define con const int
#ifdef LOCAL
#define print(x)cout<<x
#else
#define print(x)
#endif
using ld=long double;
using ll=long long;
using str=string;
template<class T,class U>ifstream&operator>>(istream&in,pair<T,U>a){return in>>a.first>>a.second;}
void fileset(str a){freopen((a+".in").c_str(),"r",stdin);freopen((a+".out").c_str(),"w",stdout);}

con inf = 0x3f3f3f3f;

int main(){
    int N, K;
    cin >> N >> K;

    rep(K){
	int X, Y;
	cin >> X >> Y;
    }

    int ans = inf;

    if (0 == (N & 1)){
	ans = N * N / 2;
    }

    for (int i = 1; i < N; i ++){
	if (0 == N % i){
	    int j = N / i;
	    if (j & 1){
		int x = i * i * (j / 2);
		int y = i * i * (j / 2 + 1);

		ans = min(ans, y * (j / 2) + x * (j / 2 + 1));
	    }
	}
    }

    cout << ans << endl;
}