Problem Description

On the conveyor line of an automated factory, there are $3N$ parts arranged in order. Each part has a marked price $a_i$: if it is recycled, this price is counted as revenue; if it is processed, this price is counted as cost.

As the person in charge of the factory area, Xiao Lan needs to choose two specific groups from these $3N$ parts:

1. Recycling group: choose exactly $N$ parts to recycle, with total revenue denoted by $R$.
2. Processing group: choose exactly $N$ parts to process, with total cost denoted by $C$.

Because the conveyor line is irreversible and moves in only one direction, the selection must follow a strict order: every recycled part must appear earlier than all processed parts in the original sequence (that is, if the indices of recycled parts are $p_1 < p_2 < \cdots < p_N$ and the indices of processed parts are $q_1 < q_2 < \cdots < q_N$, then it must hold that $p_N < q_1$).

Under this order constraint, the remaining $N$ parts on the line will be discarded directly, producing no revenue or cost.

Now Xiao Lan wants to find a plan that makes the total recycling revenue minus the total processing cost ($R - C$) as large as possible. Please compute the maximum possible value of this difference.

Input Format

The first line contains an integer $N$, representing the number of parts to be selected in each group.

The second line contains $3N$ integers $a_1, a_2, \dots, a_{3N}$, representing the marked prices of the parts on the line from left to right.

Output Format

Output one integer, representing the maximum possible value of $R - C$ under all constraints.

2
1 10 5 1 2 1

13

Hint

Sample Explanation

The optimal plan is: recycle the $2$nd and $3$rd parts, and process the $4$th and $6$th parts. Then $R = 10 + 5 = 15$, $C = 1 + 1 = 2$, and $R - C = 13$.

Constraints

For $40\%$ of the testdata, $1 \leq N \leq 1000$.

For all testdata, $1 \leq N \leq 10^5$, $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5