#include #define REP(A,B) for(int (A)=0;(A)<(B);(A)++) #define ll long long #define X first #define Y second #define pii pair #define mp make_pair #define pb push_back using namespace std; int n,m; ll solve(vector& PTS) { priority_queue< pair, vector, less > Q; ll ans = 1LL<<62; int i; ll lastpop = 1LL<<62; int lastYYY = 0; for(i=0;i < n; ) { int lastj = i; for(int j = i; j < n && PTS[j].Y==PTS[i].Y; j++) { Q.push(PTS[j]); // printf("adding %lld %lld to the heap.\n", PTS[j].X, PTS[j].Y); lastYYY = PTS[j].Y; lastj = j; } i = lastj+1; if(2*Q.size() >= n) break; } while(i < n) { while(2*Q.size() > n) { pii it = Q.top(); lastpop = min(it.X, lastpop); Q.pop(); ll x1 = it.X; while(!Q.empty()) { auto curr = Q.top(); if(curr.X != x1) break; Q.pop(); } } if(2*Q.size() == n) { pii topright = Q.top(); //printf("lastYYY=%lld, tR=%lld\n", lastYYY, topright.X); ans = min(ans, (lastYYY+1)*(topright.X+1)); } do { ll yy1 = PTS[i].Y; for(; i < n; i++) { if(PTS[i].Y != yy1) break; if(PTS[i].X < lastpop) { Q.push(PTS[i]); // printf("adding %lld %lld to the heap.\n", PTS[i].X, PTS[i].Y); lastYYY = PTS[i].Y; } } } while(i < n && 2*Q.size() < n); } while(2*Q.size() > n) { pii it = Q.top(); lastpop = min(it.X, lastpop); Q.pop(); ll x1 = it.X; while(!Q.empty()) { auto curr = Q.top(); if(curr.X != x1) break; Q.pop(); } } if(2*Q.size() == n) { pii topright = Q.top(); //printf("lastYYY=%lld, tR=%lld\n", lastYYY, topright.X); ans = min(ans, (lastYYY+1)*(topright.X+1)); } return ans; } int main() { while(scanf("%d%d", &m, &n)==2) { vector PTS; REP(i, n) { ll xxx, yyy; scanf("%lld%lld", &xxx, &yyy); PTS.pb(mp(xxx, yyy)); } vector PTS2=PTS; sort(PTS.begin(), PTS.end(), [](pii a, pii b){ return a.Y