题目描述

给你一个长度为 $3 \times n$ 的序列 $A$，序列的第 $i$ 个数大小为 $a_i$。

现在你需要从该序列中删除 $n$ 个数（不要求连续），得到一个长度为 $2 \times n$ 的序列 $A'$，使得 $A'$ 中前 $n$ 个数的和与后 $n$ 个数的和差值最大。

格式

输入格式

第一行包含一个整数 $n$；

第二行 $3 \times n$ 个用空格隔开的整数，表示序列 $A$。

输出格式

输出一行包含一个整数，表示 $A'$ 中前 $n$ 个数的和与后 $n$ 个数的和的最大差值。

样例1

输入样例1

2
3 1 4 1 5 9

输出样例1

1

样例解释

在序列 $A$ 中删除 $a_2,a_6$，得到序列 $A'$={$3,4,1,5$}，此时差值最大，为 $(3+4)-(1+5)=1$。

限制

测试点$1 \sim 4$：$n \le 10$；

测试点$5 \sim 14$：$n \le 1000$；

测试点$15 \sim 25$：$n \le 10^5$；

$100\%$的数据：$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。