题目描述

在自动化工厂的水线上，依次排列着 $3N$ 个部件。每个部件都标有一个价格 $a_i$：若执行回收，该标价即为收益；若执行处理，该标价则计为成本。

作为厂区负责人，小蓝的任务是从这 $3N$ 个部件中挑选出两批特定组别：

1. 回收组：挑选出恰好 $N$ 个部件进行回收，总收益记为 $R$。
2. 处理组：挑选出恰好 $N$ 个部件进行处理，总成本记为 $C$。

由于水线是不可逆的单向传送，挑选过程必须遵守严格的先后顺序：任何一个被回收的部件，其原始位置都必须早于所有被处理的部件（即若把回收部件的下标记为 $p_1 < p_2 < \cdots < p_N$，处理部件的下标记为 $q_1 < q_2 < \cdots < q_N$，则必须满足 $p_N < q_1$）。

在满足上述顺序的前提下，水线上剩下的 $N$ 个部件将被直接弃置，不产生任何收益或成本。

现在，小蓝希望通过合理的方案，使得回收的总收益减去处理的总成本（$R - C$）尽可能大。对此，请你计算出这个差值的最大可能结果。

输入格式

第一行包含一个整数 $N$，表示每组选取的部件数量。

第二行包含 $3N$ 个整数 $a_1, a_2, \dots, a_{3N}$，表示水线上从左到右每个部件的标价。

给定的网络可能包含重边或自环。

输出格式

输出一个整数，表示在满足所有约束的前提下，$R - C$ 的最大可能值。

2
1 10 5 1 2 1

13

提示

【样例说明】

最优的方案为：回收第 $2$、$3$ 个部件，处理第 $4$、$6$ 个部件，此时 $R = 10 + 5 = 15$，$C = 1 + 1 = 2$，$R - C = 13$。

【评测用例规模与约定】

对于 $40\%$ 的评测用例，$1 \leq N \leq 1000$。

对于所有评测用例，$1 \leq N \leq 10^5$，$1 \leq a_i \leq 10^9$。