Migrated from Lutece 2685 皇室战争

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

对于一个皇室玩家而言，等压在一定程度上会大幅度影响到最后的战果。因此对于两个人之间的战斗，我们可以通过两者的牌库来衡量最后两方战斗的精彩程度。若将两方的卡牌等级看作 $2$ 个长度为 $n$ 的序列 $\{x_i\}$, $\{y_i\}$，那两个人的比赛的精彩程度 $T$ 为

显然，从上述公式我们可以看出，$T$ 越小，比赛越为精彩。所以当我们给到两个人的牌组的时候，我们可以通过 $T$ 来预先知道比赛的精彩程度，显然牌序会很大程度上影响到双方的比赛结果，因此比赛双方都想知道通过安排初始牌序能获得的精彩程度的最大值和最小值。

但友谊赛并不是如此，友谊赛可以通过给一方的卡牌提升 $d$ 级使得 $T$ 能取到最小值，即需要求出

中 $T'$ 的最小值和此时 $d$ 的取值。这里由于系统不能给一方无限的加等级，因此整数 $d$ 的取值范围为 $d\in[-D,D]$，其中 $D$ 为系统给出来的提升系数。

Input

第一行包含一个整数 $n\ (1\le n\le 1000)$，表示两个初始牌序的长度。

第二，三行分别包含两个序列 $\{x_i\}$, $\{y_i\}\ (1\le x_i,y_i\le 1000)$。两个数字之间用一个空格分开。

第四行输入一个整数 $D\ (1\le D\le 1000)$，表示整数 $d$ 的取值范围在 $[-D,D]$。

Output

第一行输出两牌库重排序后的精彩程度的最大值和最小值，用一个空格分开。

第二行输出重排序后 $T'$ 的最小值。

Samples

3
3 2 1 
4 5 6
4

35 27
0

Note

对于样例第一行的输出：

当牌序为 $1,2,3$ 与 $4,5,6$ 时，取得最小值 $27$；

当牌序为 $3,2,1$ 与 $4,5,6$ 时，取得最大值 $35$。

对于样例第二行的输出：

当牌序为 $1,2,3$ 与 $4,5,6$，给第一个的人的牌的等级都增加 $3$ 个单位时，取得最小值 $0$。

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛