#include using namespace std; using pii=pair; using tii=tuple; using qii=tuple; using ll=long long; using ld=long double; const ll INF=1ll<<60; #define rep(i,n) for (int i=0;i<(int)(n);i++) #define all(v) v.begin(),v.end() template inline bool chmin(T &a,T b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax(T &a,T b){ if(a A,B; namespace Solver{ ll fake_score(vector &v){ __int128 a_sum=0,b_sum=0; rep(i,N){ a_sum+=(__int128)A[i]*(1ll< &ans){ vector a=A,b=B; for(auto [u,v]:ans){ a[v]=a[u]=(a[u]+a[v])/2; b[v]=b[u]=(b[u]+b[v])/2; } return floorl(2000000.0-100000.0*log10l(max(abs(C-a[0]),abs(C-b[0]))+1)); } void solve(){ vector k; rep(i,N-1){ k.push_back(i); if(i==0) k.push_back(i); } int pre_fake_score=fake_score(k); while(true){ auto now=chrono::system_clock::now(); int ms=chrono::duration_cast(now-program_start).count(); if(50<=ms) break; int x=rand_int(N),y=rand_int(N); if(x==y) continue; swap(k[x],k[y]); int new_fake_score=fake_score(k); if(new_fake_score ord(N); rep(i,N) ord[i]=i; sort(all(ord),[&](int i,int j){return k[i] start_ans; bool zero=false; rep(i,N){ if(zero&&ord[i]==0) continue; if(zero||i==N-1) start_ans.emplace_back(0,ord[i]); else{ start_ans.emplace_back(ord[i],ord[i+1]); if(ord[i+1]==0) zero=true; } } vector ans=start_ans; int pre_score=score(ans); int cnt=0; int max_score=0; vector max_score_ans; while(true){ auto now=chrono::system_clock::now(); int ms=chrono::duration_cast(now-program_start).count(); if(950<=ms) break; vector new_ans=ans; int r=mt()%4; int x=rand_int(N),y=rand_int(N); int sz=new_ans.size(); if(x==y) continue; if(y> N; A.resize(N); B.resize(N); rep(i,N) cin >> A[i] >> B[i]; Solver::solve(); }