#include using namespace std; const int nmax=1e6+42; int n; long long b; struct stick { int id; int h; long long p; }; stick inp[nmax],original_inp[nmax]; bool cmp(stick x,stick y) { return x.h>y.h; } vector outp[nmax]; set< pair > active; long long best_score=2e18; vector out[nmax]; void print() { int id=1; while(outp[id].size())id++; cerr<bomb)print(); for(int i=1;i<=cnt_out;i++) out[i].push_back(inp[i].id); active={}; int SZ=cnt_out; int id_total_smaller=0; int id_total_normal=cnt_out; if(b==1)id_total_smaller=cnt_out; for(int i=cnt_out+1;i<=n;i++) { set< pair > ::iterator it=active.lower_bound(make_pair(1LL*inp[i].h,0)); pair val; if(it==active.end()) { if(id_total_smaller0)active.insert(val); } long long score=1LL*SZ*SZ*SZ; for(int i=1;i<=cnt_out;i++) { long long total_h=0; for(auto w:out[i]) total_h+=original_inp[w].h; //cerr<<"i= "<b)cnt_out++; } for(int i=1;i<=n;i++) scanf("%lld",&inp[i].p); for(int i=1;i<=n;i++) original_inp[i]=inp[i]; sort(inp+1,inp+n+1,cmp); mt19937 rng(42); if(n>1e5)bomb=4.25; while(1) { go(cnt_out); go(n); int ok=n,not_ok=cnt_out; while(ok-not_ok>1) { int av=(ok+not_ok)/2; if(go(av)==av)ok=av; else not_ok=av; } shuffle(inp+cnt_out+1,inp+n+1,rng); } return 0; }