劣解求 hack

#include<bits/stdc++.h>
#define mid ((le+ri)>>1)
#define ls (u<<1)
#define rs ((u<<1)|1)
#define lp ls,le,mid
#define rp rs,mid+1,ri
using namespace std;
typedef long long ll;
const int N=1e6+10,M=1010,V=1000;
struct nd{
	int l,r;
	nd(){
		l=0,r=1e6;
	}
	nd(int x,int y){
		l=x,r=y;
	}
};
struct sgt{
	int mx[N<<2],t[N<<2];
	void ch(int u,int k){
		mx[u]+=k;
		t[u]+=k;
	}
	void push_down(int u){
		ch(ls,t[u]);
		ch(rs,t[u]);
		t[u]=0;
	}
	void push_up(int u){
		mx[u]=max(mx[ls],mx[rs]);
	}
	void add(int u,int le,int ri,int x,int y,int k){
		if(x<=le&&ri<=y){
			ch(u,k);
			return;
		}
		push_down(u);
		if(x<=mid) add(lp,x,y,k);
		if(y>mid) add(rp,x,y,k);
		push_up(u);
	}
	int que_pos(int u,int le,int ri,int x,int y,int k){
		if(le==ri){
			if(mx[u]>=k) return le;
			return -1;
		}
		push_down(u);
		if(x<=mid&&mx[ls]>=k){
			int w=que_pos(lp,x,y,k);
			if(w!=-1) return w;
		}
		if(y>mid&&mx[rs]>=k){
			int w=que_pos(rp,x,y,k);
			if(w!=-1) return w;
		}
		return -1;
	}
}t;
int n,a[N],b[N],c[N],s[N],cnt[N];
int l[N],r[N],d[M],tg[N];
vector<int> g[N];
vector<nd> h[N];
nd ge(int k,int x){
	if(x==(int)g[k].size()){
		return nd(g[k][x-1],n);
	}
	else if(x==0){
		return nd(1,g[k][x]-1);
	}
	return nd(g[k][x-1],g[k][x]-1);
}
void app(vector<nd> &v,int tc){
	for(nd tp:v){
//		cerr<<tp.l<<" "<<tp.r<<" "<<tc<<"\n";
		if(tp.l>tp.r) continue;
		t.add(1,1,n,tp.l,tp.r,tc);
	}
}
void rep(int k,int x){
	app(h[k],-1);
//	cerr<<k<<"\n";
	if(x==0){
		if((int)g[k].size()==0){
//			cerr<<"*1\n";
			h[k]={nd(1,n)};
		}
		else{
//			cerr<<"*2\n";
			h[k]={ge(k,0),ge(k,g[k].size())};
		}
	}
	else{
//		cerr<<"*3\n";
		h[k]={ge(k,x)};
	}
	app(h[k],1);
}
signed main(){
//	freopen("interval.in","r",stdin);
//	freopen("interval.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		g[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		s[i]=s[i-1]+b[i];
	}
	for(int i=1;i<=n;i++){
		cin>>c[i];
		d[c[i]]++;
	}
	for(int i=1;i<=n;i++){
		rep(i,0);
	}
	for(int i=1;i<=n;i++){
		l[i]=i;
		r[i]=t.que_pos(1,1,n,i,n,n);
		if(r[i]!=-1&&l[i]<=r[i]){
			tg[i]=1;
		}
		cnt[a[i]]++;
		rep(a[i],cnt[a[i]]);
	}
	ll ans=1e18;
	for(int i=1;i<=n;i++){
		if(!tg[i]) continue;
		int pos=l[i];
		int h=r[i];
//		cerr<<i<<" "<<l[i]<<" "<<r[i]<<"\n";
		ll res=0;
		for(int j=1;j<=V;j++){
			if(pos+d[j]-1<=h){
				res+=1ll*j*(s[pos+d[j]-1]-s[pos-1]);
				pos+=d[j];
			}
			else{
				res+=1ll*j*(s[h]-s[pos-1]);
				break;
			}
			if(res>=ans) break;
		}
		ans=min(ans,res);
	}
	cout<<ans<<"\n";
}