#pragma GCC optimize("Ofast") #pragma GCC target("avx2") char*mmap(); #define rd_skip() while(*rp++>=48) #define rd(v) int v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;} #define rd_long(v) long v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;} #define WTHI(v) {long _z=v,_n=0,_d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;} #define WTLO(v) {long _z=v,_n=8,_d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(long*)wp=_d;wp+=8;} #define wt(v) if(v>=100000000){WTHI(v/100000000);WTLO(v);}else{WTHI(v);} #define rep(v,e) for(int v=0;v>8|a[i]<<56; } } long rsbuf[1<<16]; void radix_sort(unsigned long*a,int n){ radix_sort_aux(a,rsbuf,n); radix_sort_aux(rsbuf,a,n); radix_sort_aux(a,rsbuf,n); radix_sort_aux(rsbuf,a,n); radix_sort_aux(a,rsbuf,n); for(int i=0;i>24; } } long d1[1<<16],d2[1<<16]; main(){ char*rp=mmap(0l,1l<<28,1,2,0,0ll); rd(n); int n1=n>>1; int n2=n-n1; long off=0; int k1=1; rep(i,n1){ rd_long(a); rd_long(b); off+=b; a+=b; rep(j,k1){ d1[j+k1]=d1[j]+a; } k1<<=1; } radix_sort(d1,k1); int k2=1; rep(i,n2){ rd_long(a); rd_long(b); off+=b; a+=b; rep(j,k2){ d2[j+k2]=d2[j]+a; } k2<<=1; } radix_sort(d2,k2); long r=1l<<62; int j1=0; int j2=k2-1; while(j1=0){ long d=d1[j1]+d2[j2]-off; long a=d>=0?(--j2,d):(++j1,-d); chmin(r,a); } char wbuf[32],*wp=wbuf; wt(r); write(1,wbuf,wp-wbuf); _exit(0); }