P17708 [ICPC 2019 Nanjing R] Spy

随着时间的推移，BDN Collegiate Progranuning Contest 的教练们分裂成了两个阵营。巨大的危险在于，当乐观派与悲观派激战时，这个地区的环境变得日益分裂：少数拥有杰出学生资源的大学被一大片被忽视的停滞群体所包围。 Amy 和 Bob 分别作为这两个阵营的关键人物，决定结束这场对抗。目前，双方阵营各自拥有 $n$ 名码农和 $n$ 名送茶工，作为手中最后的资源。他们将两两组队，每支队伍由一名码农和一名送茶工组成。一支队伍的实力被视为两名成员的实力之和。 现在 Bob 雇佣了一名间谍，并获得了对手计划的一些信息：敌方阵营将派出的每支队伍的实力，以及 Bob 击败这支队伍后能获得的相应声誉单位数。自然而然地，他希望能够最佳地安排己方的队伍，以获取更多的声誉。 这两个阵营即将发生冲突，他们的队伍将**以随机顺序一对一**进行战斗。也就是说，在这次冲突中可能出现 $n!$ 种不同的对战情况。实力较高的队伍将凯旋而归。当两支实力相同的队伍相遇时，由 Amy 率领的队伍将以微弱优势击败对手。 你能计算出 Bob 将获得的期望声誉的最大值吗？为了使答案成为一个整数，你需要将答案乘以 $n$，并且我们保证期望值乘以 $n$ 后总是一个整数。

输入包含五行，第一行由一个整数 $n~(1 \le n \le 400)$ 组成。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，满足 $-10^{18} \leq a_i \leq 10^{18}$，表示由 Amy 率领的所有队伍的实力。 第三行包含 $n$ 个整数 $p_1, p_2, \cdots, p_n$，满足 $1 \leq p_i \leq 10000$，表示 Bob 击败这些由 Amy 率领的队伍所能获得的对应声誉单位数。 第四行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n$，满足 $-10^{18} \leq b_i \leq 10^{18}$，表示 Bob 阵营中所有码农的实力。 最后一行包含 $n$ 个整数 $c_1, c_2, \cdots, c_n$，满足 $-10^{18} \leq c_i \leq 10^{18}$，表示 Bob 阵营中所有送茶工的实力。

在一行中输出一个整数，表示最大期望获胜次数乘以 $n$ 的结果。

翻译由 DeepSeek V4 Pro 完成