配点 : $500$ 点

問題文

$N$ を $1$ 以上の整数とします。

長さ $3N$ の数列 $a = (a_1, a_2, ..., a_{3N})$ があります。 すぬけ君は、$a$ からちょうど $N$ 個の要素を取り除き、残った $2N$ 個の要素を元の順序で並べ、長さ $2N$ の数列 $a'$ を作ろうとしています。 このとき、$a'$ のスコアを $(a' の前半 N 要素の総和) - (a' の後半 N 要素の総和)$ と定義します。

$a'$ のスコアの最大値を求めてください。

制約

• $1 \leq N \leq 10^5$
• $a_i$ は整数である。
• $1 \leq a_i \leq 10^9$

部分点

• $300$ 点分のテストケースでは、$N \leq 1,000$ が成り立つ。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $a_2$ $...$ $a_{3N}$

出力

$a'$ のスコアの最大値を出力せよ。

2
3 1 4 1 5 9

1

$a_2$, $a_6$ を取り除くと、$a' = (3, 4, 1, 5)$ となり、スコアは $(3 + 4) - (1 + 5) = 1$ となります。

1
1 2 3

-1

例えば、$a_1$ を取り除くと、$a' = (2, 3)$ となり、スコアは $2 - 3 = -1$ となります。

3
8 2 2 7 4 6 5 3 8

5

例えば、$a_2$, $a_3$, $a_9$ を取り除くと、$a' = (8, 7, 4, 6, 5, 3)$ となり、スコアは $(8 + 7 + 4) - (6 + 5 + 3) = 5$ となります。