{"raw_statement":[{"iden":"problem statement","content":"Let $N$ be a positive integer.\nThere is a numerical sequence of length $3N$, $a = (a_1, a_2, ..., a_{3N})$. Snuke is constructing a new sequence of length $2N$, $a'$, by removing exactly $N$ elements from $a$ without changing the order of the remaining elements. Here, the score of $a'$ is defined as follows: $($the sum of the elements in the first half of $a') - ($the sum of the elements in the second half of $a')$.\nFind the maximum possible score of $a'$."},{"iden":"constraints","content":"*   $1 ≤ N ≤ 10^5$\n*   $a_i$ is an integer.\n*   $1 ≤ a_i ≤ 10^9$"},{"iden":"partial score","content":"*   In the test set worth $300$ points, $N ≤ 1000$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $...$ $a_{3N}$"},{"iden":"sample input 1","content":"2\n3 1 4 1 5 9"},{"iden":"sample output 1","content":"1\n\nWhen $a_2$ and $a_6$ are removed, $a'$ will be $(3, 4, 1, 5)$, which has a score of $(3 + 4) - (1 + 5) = 1$."},{"iden":"sample input 2","content":"1\n1 2 3"},{"iden":"sample output 2","content":"\\-1\n\nFor example, when $a_1$ are removed, $a'$ will be $(2, 3)$, which has a score of $2 - 3 = -1$."},{"iden":"sample input 3","content":"3\n8 2 2 7 4 6 5 3 8"},{"iden":"sample output 3","content":"5\n\nFor example, when $a_2$, $a_3$ and $a_9$ are removed, $a'$ will be $(8, 7, 4, 6, 5, 3)$, which has a score of $(8 + 7 + 4) - (6 + 5 + 3) = 5$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}