P2460 [SDOI2007] Kobe's Match

There are $m + 1$ participants in total, including Kobe. Each of the other $m$ participants has an ability value $s_i$. Kobe will play $n$ matches. In each match, he faces one opponent who has not been defeated before. Once Kobe defeats someone, that opponent will no longer participate. Kobe’s probability of defeating a specific opponent varies by match index. Specifically, you are given an $n \times m$ matrix $v_{i,j}$, where $v_{i,j}$ is the probability that Kobe defeats opponent $j$ if they meet in match $i$. Choose the opponent Kobe faces in each of the $n$ matches (without repetition) to maximize the probability that Kobe wins all $n$ matches. Subject to achieving this maximum probability (with an error not exceeding $10^{-10}$), maximize the sum of the ability values of the opponents that Kobe defeats.

- The first line contains two positive integers $n, m$. - The second line contains $m$ integers, the ability values $s_i$ of the other $m$ participants. - Then follows an $n \times m$ matrix, the probabilities $v_{i,j}$.

- On the first line, output the maximum probability that Kobe wins all $n$ matches. The error must not exceed $10^{-10}$. - On the second line, output the maximum sum of ability values among all strategies that achieve the maximum probability.

Constraints $1\le n\le 10, n \le m \le 10^5$； $1\le s_i\le 100, 0\le v_{i,j}\le 1$。 This problem is Special Judge. Translated by ChatGPT 5