9455: Malfunctioning Typewriter

Recently, Bobo, having some free time, wants to write a poem. His method of writing poems is straightforward: he carefully selects $n$ verses, where each verse is a binary string of length $m$ and all $n$ verses are distinct. He then considers **any** concatenation of these $n$ verses in any order to form a binary string of length $nm$ as a good poem. Unfortunately, Bobo only has a broken typewriter. When Bobo tries to type $x$ (where $x$ is either $0$ or $1$) on paper, the typewriter has a probability $p$ ($0.5\leq p<1$) of typing $x$ correctly and a probability $1-p$ of typing $1−x$. Bobo wants to know, using the optimal strategy, what is the maximum probability that he can write a good poem?

The first line of input contains three integers $n,m,p$ ($1\leq n\leq 1000,1\leq m\leq 1000,0.5\leq p<1$), which represent the number of verses, the length of each verse, and the probability that the typewriter works correctly, respectively. The probability $p$ is guaranteed to have at most six decimal places. Then $n$ lines follow, with the $i$\-th line $(1\leq i\leq n)$ containing a binary string of length $m$, representing the content of the $i$\-th verse. It is guaranteed that the $n$ verses are distinct.

Output a single number in a line, representing the maximum probability that Bobo can write a good poem using the optimal strategy. Your answer will be considered correct if and only if its absolute or relative error does not exceed $10^{-9}$. Formally, if the correct answer is $a$ and your output is $b$, then your answer will be considered correct if and only if $\frac{|a-b|}{\max(b,1)}\leq 10^{-9}$.

##### 样例一解释：The only good poem that meets Bobo's requirements is $000$. In this case, every time Bobo presses $0$ or $1$, there is always a $0.5$ probability of getting the desired $0$. Under the optimal strategy, there is a probability of $(0.5)^3=0.125$ of producing a good poem. #### 样例二输入 ``` 2 3 0.9 010 101 ``` #### 样例二输出 ``` 0.590490000000 ``` #### 样例三输入 ``` 4 2 0.618 00 01 10 11 ``` #### 样例三输出 ``` 0.201586731534 ```