题目描述

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}$.官方中文