Spy

Over time, those coaches in BDN Collegiate Progranuning Contest split into two camps.The big danger is that, while optimists and pessimists battle it out, the environment of this area becomes ever more divided between universities with outstanding student resources surrounded by a vast neglected group of stagnation.

Amy and Bob, as the linchpins of these two camps respectively, decided to put the end to the rival. Now both camps hold nnn coders and nnn tea-bringers as the last resource on hand. They will form teams in pair that each team should consist of a coder and a tea-bringer. The power of a team is regarded as the sum of powers of both members.

Now Bob hired a spy and has got some information about the plan of his rival: the power of each team which will present for the enemy camp, and the corresponding unit of reputations that Bob would gain after beating this team. Naturally, he hopes to make the best arrangement of teams in his camp for more reputations.

These two camps will have a collision soon, and their teams will fight one on one in random order. That is, we may have n!n!n! different situations appearing in this collision. A team would triumphantly return if it has a higher power. When two teams of the same power meet, the one led by Amy would beat the rival by a neck.

Can you calculate the maximum expected unit of reputations that Bob will gain? To make the answer be an integer, you are asked to multiply the answer by nnn and we guarantee that the expected number multiplied by nnn should always be an integer.

Input

The input contains five lines, and the first line is consist of an integer n (1≤n≤400)n~(1\le n \le 400)n (1≤n≤400).

The second line contains nnn integers a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​ with −1018≤ai≤1018-10^{18}\leq a_i\leq 10^{18}−1018≤ai​≤1018, indicating the powers of all the teams led by Amy.

The third line contains nnn integers p1,p2,⋯ ,pnp_1,p_2,\cdots,p_np1​,p2​,⋯,pn​ with 1≤pi≤100001\leq p_i\leq 100001≤pi​≤10000, indicating the corresponding units of reputations that Bob would gain if these teams led by Amy are beaten.

The fourth line contains nnn integers b1,b2,⋯ ,bnb_1,b_2,\cdots,b_nb1​,b2​,⋯,bn​ with −1018≤bi≤1018-10^{18}\leq b_i\leq 10^{18}−1018≤bi​≤1018, indicating the powers of all coders in the camp of Bob.

The last line contains nnn integers c1,c2,⋯ ,cnc_1,c_2,\cdots,c_nc1​,c2​,⋯,cn​ with −1018≤ci≤1018-10^{18}\leq c_i\leq 10^{18}−1018≤ci​≤1018, indicating the powers of all tea-bringers in the camp of Bob.

Output

Output an integer in a single line indicating the maximum expected number of wins multiplied by nnn.

明显的暴力匹配，不过需要带权值。所以是KM算法。

网上很多KM的板子都是 n ^ 4 的复杂度，这道题我们需要 n ^ 3 的复杂度才能过。需要用slack数组来优化。

这道题不能费用流，费用流不一定是最大权值匹配，费用流是在保证最大流的时候最大权值。

并且费用流复杂度也过不去。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=410;
int w[N][N],a[N],b[N],c[N],p[N],n;
int lx[N],ly[N],visy[N],slack[N],pre[N],link[N];
int bfs(int k){
	int x,y=0,yy=0,delta;
	memset(pre,0,sizeof pre);
	for(int i=1;i<=n;i++)	slack[i]=inf;
	link[y]=k;
	while(1){
		x=link[y],delta=inf,visy[y]=1;
		for(int i=1;i<=n;i++){
			if(!visy[i]){
				if(slack[i]>lx[x]+ly[i]-w[x][i]){
					slack[i]=lx[x]+ly[i]-w[x][i]; pre[i]=y;
				}
				if(slack[i]<delta) delta=slack[i],yy=i;
			}
		}
		for(int i=0;i<=n;i++){
			if(visy[i])	lx[link[i]]-=delta,ly[i]+=delta;
			else	slack[i]-=delta;
		}
		y=yy;
		if(link[y]==-1)	break;
	}
	while(y)	link[y]=link[pre[y]],y=pre[y];
}
int KM(){
	memset(link,-1,sizeof link);
	for(int i=1;i<=n;i++){
		memset(visy,0,sizeof visy); bfs(i);
	}
	int res=0;
	for(int i=1;i<=n;i++)	if(link[i])	res+=w[link[i]][i];
	return res;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++)	cin>>p[i];
	for(int i=1;i<=n;i++)	cin>>b[i];
	for(int i=1;i<=n;i++)	cin>>c[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int val=0;
			for(int k=1;k<=n;k++)	if(b[i]+c[j]>a[k])	val+=p[k];
			w[i][j]=val;
		}
	}
	cout<<KM()<<endl;
	return 0;
}