Description

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.

Input Format

• 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}$.

Output Format

• 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.

3 4
91 92 93 94
0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5

0.125
279

Hint

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