分数: 500 点
问题陈述
让 N 是正整数。
有一个长度为的数字序列 3N, a = (a_1, a_2, ..., a_{3N})。 Snuke 正在构造一个新的长度序列 2N, a',通过精确删除 N 元素来自 a 不改变剩余元素的顺序。 这里,得分为 a' 定义如下: (前半部分元素之和 a') - (后半部分的元素之和 a').
找出 的最大可能分数 a'.
约束
- 1 ≤ N ≤ 10^5
- a_i 是一个整数。
- 1 ≤ a_i ≤ 10^9
部分分数
- 在测试集中值得 300 点, N ≤ 1000.
输入
输入由标准输入按以下格式给出:
N
a_1 a_2 ... a_{3N}
输出
打印最大可能分数 a'.
示例输入 1
2 3 1 4 1 5 9
示例输出 1
1
当 a_2 和 a_6 被删除, a' 将是 (3, 4, 1, 5),其得分为 (3 + 4) - (1 + 5) = 1.
示例输入 2
1 1 2 3
示例输出 2
-1
例如,当 a_1 被删除, a' 将是 (2, 3),其得分为 2 - 3 = -1.
示例输入 3
3 8 2 2 7 4 6 5 3 8
示例输出 3
5
例如,当 a_2, a_3 和 a_9 被删除, a' 将是 (8, 7, 4, 6, 5, 3),其得分为 (8 + 7 + 4) - (6 + 5 + 3) = 5.