#include <iostream>
#include <set>
#include <utility>
#include <algorithm>
#include <iterator>

using namespace std;

/*
long long f1(const multiset<long long> &mset, long long many) {
	long long high=1000000047LL, low=0;
	long long mid;
	
	if (mset.size()<many) return -1;
	if (mset.size()==many) return *(mset.rbegin());
	
	while (high>low+1) {
		mid=(high+low)/2;
		multiset<long long>::iterator it = mset.upper_bound(mid);
		
		if (distance(mset.begin(), it)==many) {
			multiset<long long>::iterator it2=mset.upper_bound(mid);
			it2--;
			return (*it2);
		}
		if (distance(mset.begin(), it) > many) high=mid;
		else low=mid;
	}
	return -1;
}
*/

long long f1(multiset<long long> &mset, long long many) {	
	if (mset.size()<many) return -1;
	if (mset.size()==many) return *(mset.rbegin());
	
	while (mset.size()>many) {
		multiset<long long>::iterator it = mset.end();
		mset.erase(--it);
	}
	return *(mset.rbegin());
}

int main() {
	int n; 
	long long m;
	while (cin>>m>>n) {
		vector<pair<long long, long long> > input(n);
		multiset<long long> mset;
		
		for (int i=0; i<n; i++) cin>>input[i].first>>input[i].second;
		sort(input.begin(), input.end());
		
		int k=0;
		mset.insert(input[k++].second);
		
		long long best=-1;
		
		do {
			while (k<n && input[k].first==input[k-1].first) mset.insert(input[k++].second);
			long long high=f1(mset, n/2);
			
			if (high!=-1) {
				if (best==-1) best=(input[k-1].first+1)*(high+1);
				else best=min(best, (input[k-1].first+1)*(high+1));
			} 
			if (k<n) mset.insert(input[k++].second);
		} while (k<n);
		
		if (n%2==1 || best==-1) cout<<-1<<endl;
		else cout<<best<<endl;
	}
	
	return 0;
}