Migrated from Lutece 2715 二分图匹配

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有两个点数均为 $n$ 的带权点集 $A,B$ ，点集之间的点会相互连边，而点集内的点不会连边。

显然我们可以知道，这一定是个二分图。

但现在，它们之间的边全部断开了，并且又来了一个有着 $n$ 个点的带权点集 $C$。这时候原来的两个点集将会一一配对形成新的只有 $n$ 个点的点集 $D$ ，每个点的权值为两个点的权值之和。

接着它会跟新点集进行随机的一一配对。对于每个配对，如果来自 $D$ 的点 $d_i$ 权值大于来自 $C$ 中的点的权值 $c_i$，则其获得 $w_i$ 的得分。

由于后一过程是随机的，因此得到的得分有很多种可能，现在你想知道，在你能规划 $A,B$ 的最优匹配方案下，能获得的得分的期望是多少，并输出期望乘 $n$ 之后的答案，显然我们可以知道这个答案是一个整数

Input

输入共 $5$ 行 第一行输入点集大小 $n$ 第二行输入带权点集 $C$ 中各点的权值 $c_i$ 第三行输入带权点集 $C$ 中各点的积分 $w_i$ 第四行输入带权点集 $A$ 中各点的权值 $a_i$ 第五行输入带权点集 $B$ 中各点的权值 $b_i$

Output

输出共一行，输出期望得分乘 $n$ 后的结果

Samples

2
0 1
1 1
0 1
0 2

3

Constraints

对于全部数据

$1 \leq n \leq 400$

$-10^{18} \leq a_i, b_i ,c_i \leq 10^{18}$

$1 \leq w_i \leq 10000$

Note

题目名字≠做法，但正解需要二分图匹配的基础知识

若超时，请检查做法or代码的复杂度是否正确

Resources

2022 UESTC ICPC Training for Graph