题目描述

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

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

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

输入格式

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

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

输出格式

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

题目大意

给一个长度为 $3N$ 的数组 $a=(a_1,a_2,...,a_n)$，要求删去其中 $N$ 个数使得剩余的 $2N$ 个数中前 $N$ 个数之和与后 $N$ 个数之和的差最大。

2
3 1 4 1 5 9

1

1
1 2 3

-1

3
8 2 2 7 4 6 5 3 8

5

提示

制約

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

部分点

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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