Problem B
Balls and Bins

In the balls and bins game, you toss balls into bins and try to earn some prize money.

In front of you are $N$ bins. Each turn, you throw a ball into one of the bins. Unfortunately your aim is not so precise; maybe it is because the bins are so far away. So, in each turn the ball will land in one of the bins uniformly at random, meaning for each ball you throw and each $1 \leq i \leq N$, the probability that the ball lands in bin $i$ is exactly $1/N$; this is independent of where your previous throws landed. At least you are guaranteed that the throw will land in some bin.

After you throw a ball into the bin, it stays in that bin. If you ever throw a ball into a bin that already has exactly $3$ balls, you are forced to quit and win no money. At any point before you throw a ball, if you have not yet been forced to quit you may then choose to quit and keep your earnings.

Finally, each throw of the ball has some value. That is, for each $1 \leq i \leq 3\cdot N$, if you throw ball $i$ and it lands in a bin with $\leq 2$ balls, you earn $p_ i$ dollars in addition to what you have earned so far.

Suppose you play the game optimally to maximize your expected profit, meaning at each step you make a choice (toss the ball or quit) optimally to maximize your expected winnings. What will you earn in expectation if you play this game?

Input

The first line of input contains a single integer $N$ $(1 \leq N \leq 100)$ indicating the number of bins. The second line contains $3\cdot N$ space-separated integers $p_1, p_2, \ldots , p_{3 \cdot N}$ where $p_ i$ $(0 \leq p_ i \leq 100\, 000)$ is the amount of money you will earn if you successfully toss the $i$’th ball into a bin that has $\leq 2$ balls.

Output

Output a single value indicating the expected profit you will receive if you play optimally. Your answer will be accepted if it is correct within an absolute or relative error of $10^{-5}$.

1
1 2 3

6.0000000000000000

2
1 1 1 1 1 1

4.1250000000000000

3
2 1 2 1 2 3 2 3 10000

854.8940710257579667