P16276 [Lanqiao Cup 2026 NOI Qualifier C] Recycling and Processing

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.

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 one integer, representing the maximum possible value of $R - C$ under all constraints.

### 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