← 返回题目列表

AtCoder · arc074_b

D. 3N 个数字

中文机器翻译题面 查看原题

分数: 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.