B. Emang Harusnya Bet Merah
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Assume you are a highly intelligent person that has perfect logic. Hence, you will not gamble under any circumstances, but this time you are forced to and have no choice.

You are given $$$N$$$ dice, each dice has $$$M$$$ faces. Let the number on the $$$j$$$-th face of the $$$i$$$-th dice be $$$A_{i,j}$$$.

Initially, all dice are not locked. You have exactly $$$N$$$ turns to make all dice locked in the end. Each turn is the following steps:

  1. Roll all dice that are not locked. For each dice that's rolled, each of the $$$M$$$ faces has an equal probability to show up.
  2. Then, after seeing the faces, you choose exactly one dice to lock. This locked dice will remain locked until the end of the game and can't be relocked.

The final score is the sum of values on the shown faces of all dice in the end.

Being the perfect logician you are, in any situation, you'll always do moves that maximizes your expected final score. What is the expected value of your score?

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 12$$$; $$$1 \leq M \leq 1000$$$) — the number of dice and the number of faces for each dice.

The $$$i$$$-th of the next $$$N$$$ lines contains $$$M$$$ integers $$$A_{i,1}, A_{i,2}, \ldots, A_{i,M}$$$ ($$$1 \leq A_{i,j} \leq 10^9$$$) — the value in each face for the $$$i$$$-th dice.

Output

A single real number representing the expected value of your score.

Your answer is considered correct if the relative or absolute error of your answer doesn't exceed $$$10^{-4}$$$. Formally, let your answer be $$$a$$$ and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,b)}\leq10^{-4}$$$.

Examples
Input
2 2
1 3
2 2
Output
4.5000000000
Input
4 5
8 7 6 5 7
2 3 4 5 3
1 8 8 8 8
7 7 8 7 6
Output
26.6129577984
Note

In the first example, after the first roll, the two possible configurations of values shown on the two dice are $$$[1,2]$$$ and $$$[3,2]$$$, each having a probability of $$$\frac{1}{2}$$$ of happening.

  1. If $$$[1,2]$$$ shows up, it's better to lock dice $$$2$$$. After that, you roll dice $$$1$$$, which itself can result in a value of $$$1$$$ or $$$3$$$ with equal probability. This means, the final configurations $$$[1,2]$$$ and $$$[3,2]$$$ from this scenario each has an overall probability of $$$\frac{1}{4}$$$.
  2. If $$$[3,2]$$$ shows up, it's better to lock dice $$$1$$$. After that, you roll dice $$$2$$$, which itself always results in a value of $$$2$$$. This means, the final configuration $$$[3,2]$$$ from this scenario has an overall probability of $$$\frac{1}{2}$$$.

The expected value of the total score overall is $$$(1+2)\times\frac{1}{4}+(3+2)\times\frac{1}{4}+(3+2)\times\frac{1}{2}=4.5$$$.