随着时间的推移，BDN 大学生程序设计竞赛的教练们分成了两个阵营。巨大的危险在于，当乐观派和悲观派争斗不休时，该地区的环境变得越来越分裂，拥有杰出学生资源的大学被一大群被忽视的停滞群体所包围。

Amy 和 Bob 分别作为这两个阵营的核心人物，决定结束这种竞争。现在，两个阵营手中最后的资源都是 $n$ 名程序员和 $n$ 名茶水员。他们将两两组队，每支队伍由一名程序员和一名茶水员组成。队伍的战力被视为两名成员战力之和。

现在，Bob 雇佣了一名间谍，并获得了一些关于对手计划的情报：敌方阵营将派出的每支队伍的战力，以及 Bob 在击败这些队伍后将获得的相应声望值。自然地，他希望为自己的阵营做出最佳的队伍安排，以获得更多的声望。

这两个阵营很快就会发生碰撞，他们的队伍将以随机顺序进行一对一的对抗。也就是说，在这种碰撞中可能会出现 $n!$ 种不同的情况。如果一支队伍的战力更高，它就会获胜。当两支战力相同的队伍相遇时，由 Amy 领导的队伍会以微弱优势击败对手。

你能计算出 Bob 将获得的最大期望声望值吗？为了使答案成为整数，请将答案乘以 $n$，我们保证期望值乘以 $n$ 后始终为整数。

输入格式

输入包含五行。第一行包含一个整数 $n$ ($1 \le n \le 400$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^{18} \le a_i \le 10^{18}$)，表示 Amy 领导的所有队伍的战力。

第三行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10\,000$)，表示如果击败这些由 Amy 领导的队伍，Bob 将获得的相应声望值。

第四行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($-10^{18} \le b_i \le 10^{18}$)，表示 Bob 阵营中所有程序员的战力。

最后一行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($-10^{18} \le c_i \le 10^{18}$)，表示 Bob 阵营中所有茶水员的战力。

输出格式

输出一个整数，表示最大期望声望值乘以 $n$ 的结果。

样例

输入 1

4
1 2 3 4
1 1 1 1
0 0 1 1
0 1 1 2

输出 1

3