C. Game on Venus
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is 2067 and the fine astronauts Adrian and Ashton just landed on Venus, marking a significant step forward in space exploration for mankind! However, they are currently having a dispute trying to figure out who should get the honor of being the first to touch down on the surface. To prevent further arguing, their advisor Maverick suggests that they play the following game to decide.

In this game, there is an array $$$a$$$ of $$$3n$$$ $$$(1 \leq n \leq 10^5)$$$ numbers. In each round:

  • Adrian may (or may not) $$$\textbf{cyclically shift}^\dagger$$$ the array any number of times.
  • Adrian then will select two indices $$$i, j$$$ in the array such that they are not next to each other ($$$i \lt j$$$ and $$$|i - j| \neq 1$$$). He will add $$$a[i] + a[j]$$$ to his score (the values at these indices).
  • Ashton then will select an index $$$k$$$ between $$$i,j$$$ ($$$i \lt k \lt j$$$) and add $$$3 * a[k]$$$ to his score.
  • After this, elements at indices $$$i, j, k$$$ are removed from the array.

This process repeats until there are no elements left in $$$a$$$, at which point the game ends.

Adrian and Ashton both want to maximize their score, as the player with the higher score at the end of the game wins. If Adrian and Ashton play optimally, what score will both of them have at the end of the game?

$$$^\dagger$$$Given an array $$$a$$$ of size $$$k$$$, a cyclic shift of $$$a$$$ turns $$$[a_1, a_2, ..., a_{k-1}, a_k]$$$ into $$$[a_k, a_1, a_2, ..., a_{k-1}]$$$

Input

The first line contains an integer $$$n$$$, where $$$a$$$ is of size $$$3n$$$

The second line contains $$$3n$$$ integers, $$$[a_1, a_2, ... a_{3n}]$$$ $$$(1 \leq a_i \leq 10^9$$$), the elements in $$$a$$$.

Output

Output two numbers, Adrian's score and Ashton's score if both play optimally.

Examples
Input
1
10 5 10
Output
20 15
Input
2
3 8 5 4 10 1
Output
27 12
Note

In the first test case, in the first round it is optimal for Adrian to leave the array as is and select indices $$$i = 1, j = 3$$$. Thus Ashton only has one choice for $$$k$$$, which is $$$2$$$.

After this round, Adrian's score is $$$10 + 10 = 20$$$, and Ashton's score is $$$5 * 3 = 15$$$.

After removing indices $$$1, 2, 3$$$ from the array, it is empty, and thus the game ends. So these are Adrian and Ashton's final scores.

In the second test case, one sequence of operations leading to the optimal scoring is as follows:

Round 1:

  • Adrian cyclically shifts the array twice, making it $$$[10, 1, 3, 8, 5, 4]$$$
  • Adrian selects $$$i = 1, j = 4$$$, and Ashton selects $$$k = 3$$$
  • Adrian's score is now $$$10 + 8$$$, Ashtons score is now $$$3 * 3$$$
  • After removing these indices from the array, we are left with $$$[1, 5, 4]$$$
Round 2:
  • Adrian cyclically shifts the array once, making it $$$[4, 1, 5]$$$
  • Adrian selects $$$i = 1, j = 3$$$, and Ashton selects $$$k = 2$$$
  • $$$4 + 5$$$ is added to Adrian's score, and $$$1 * 3$$$ is added to Ashton's score.
  • After removing these indices from the array, it is now empty, and the game ends

Thus Adrian's score at the end is $$$10 + 8 + 4 + 5 = 27$$$, and Ashton's score is $$$3 * 3 + 1 * 3 = 12$$$.