#include "job.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
int par[1<<18];
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
void merge(int a,int b){
a=abp(a+2),b=abp(b+2);
par[b]=a;
}
int comp(int n){
return abp(n+2)-2;
}
} DDT;
struct DATA{
long long timetaken,value,i;
DATA(long long u,long long d,int ind){
value=u,timetaken=d,i=ind;
}
DATA(){
timetaken=1e9;
value=1;
i=-1;
}
friend bool operator<(const DATA &a,const DATA&b){
return make_pair(a.timetaken*b.value,a.i)<
make_pair(b.timetaken*a.value,b.i);
}
};
set<DATA>pq;
long long scheduling_cost(std::vector<int> p, std::vector<int> _u, std::vector<int> _d) {
vector<long long>u,d;
int N=p.size();
long long curtime=0,ans=0;
for(int i=0;i<N;i++)
u.push_back(_u[i]),
d.push_back(_d[i]),
ans+=u[i]*d[i];
for(int i=0;i<N;i++)
pq.insert(DATA(u[i],d[i],i));
while(pq.size()){
int i=pq.begin()->i;
pq.erase(DATA(u[i],d[i],i));
if(DDT.comp(p[i])==-1){
ans+=curtime*u[i];
curtime+=d[i];
DDT.merge(-1,i);
} else {
int mer=DDT.comp(p[i]);
pq.erase(DATA(u[mer],d[mer],mer));
DDT.merge(mer,i);
ans+=d[mer]*u[i];
u[mer]+=u[i];d[mer]+=d[i];
pq.insert(DATA(u[mer],d[mer],mer));
}
}
return ans;
}
