题目描述

给你一个长度为 \(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\)。