# Problem A

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}$.

Sample Input 1 | Sample Output 1 |
---|---|

1 1 2 3 |
6.0000000000000000 |

Sample Input 2 | Sample Output 2 |
---|---|

2 1 1 1 1 1 1 |
4.1250000000000000 |

Sample Input 3 | Sample Output 3 |
---|---|

3 2 1 2 1 2 3 2 3 10000 |
854.8940710257579667 |