D. Dice Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

ETH math majors Alice and Bob are playing a game with dice. There are $$$n$$$ dice, each of the same, custom design, on the table. The game lasts $$$k$$$ turns; on a player's turn, that player picks up any subset of the dice, and rerolls them.

Alice starts, and plays on odd-numbered turns (including the first turn). Bob plays on even-numbered turns. Alice wants to maximize the sum of values the dice show at the end of the game, and Bob wants to minimize the sum. Assuming both players play optimally, what is the expected sum of values of the dice at the end of the game?

Input

The first line contains three integers $$$1 \leq n, m, k \leq 10^5$$$: the number of dice, the number of faces on the custom type of dice, and the number of rounds the game lasts.

The second line contains $$$m$$$ integers $$$f_1, \dots, f_m$$$ ($$$1 \leq f_i \leq 10^9$$$): the values on the faces of the custom type of dice used.

The third line contains $$$n$$$ integers $$$v_1, \dots, v_n$$$ ($$$v_i \in \{f_1, \dots, f_m\}$$$): the initial values of each of the $$$n$$$ dice.

Output

Output one real number: the expected sum of values of the dice at the end of the game, assuming both players play optimally.

Your answer is considered correct if its absolute or relative difference to the correct answer is at most $$$10^{-9}$$$. More formally, let $$$a$$$ be your answer and $$$c$$$ the correct answer. Your output is considered correct if $$$|a - c| / \max(1, c) \leq 10^{-9}$$$.

Examples
Input
2 6 2
1 2 3 4 5 6
1 4
Output
6.2500000000
Input
1 3 10
1 1 3
3
Output
1.2866432962
Note

After a dice is rolled, its value will be an uniformly random one among the $$$m$$$ values $$$f_1, \dots, f_m$$$.