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

using namespace std;

/*
bool msort1(const pair<long long, long long> &l, const pair<long long, long long> &r) {
	if (l.first==r.first) return (bool)(l.second<r.second);
	else return (bool)(l.first<r.first);
}*/

long long f1(const multiset<long long> &mset, long long many) {
	long long high=1000000047LL, low=0;
	long long mid;
	
	//cout<<"mset size:"<<mset.size()<<endl;
	
	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;
		//cout<<low<<" "<<high<<endl;
	}
	return -1;
}

int main() {
	/*
	multiset<int> mset;
	multiset<int>::iterator i = mset.insert(1);
	mset.insert(1);
	multiset<int>::iterator i2=mset.insert(1);
	
	mset.insert(4);
	
	multiset<int>::iterator i3=mset.upper_bound((*i2)+1);
	i3--;
	
	for (; i3!=mset.end(); i3++) cout<<*i3<<" ";
	
	cout<<distance(mset.begin(), mset.end())<<endl;
	*/
	
	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());
		//for (int i=0; i<n; i++) cout<<input[i].first<<"|"<<input[i].second<<"  ";
		
		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);
			
			//cout<<"at x="<<input[k-1].first<<" we have hight="<<high<<endl;
			
			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;
		//cout<<"END"<<endl;
		// IF 2|not n FUCK THEM
	}
	
	return 0;
}