725. [SDOI 2007] 科比的比赛

【题目描述】

NBA球星云集，谁是最厉害的呢？没有定论。

Nba总裁大卫*斯特恩最近闲得无聊，决定举办一场球员单挑大赛。

比赛是这样的:首先，我们给每人都打上个分数，表示了每个人的整体能力。然后让每个参赛队员都打n场比赛，首先看谁赢得最多，然后看谁打赢的人的能力值的和最大。

本人一向支持科比(我不支持),当然希望他赢。现在让我们和科比一起去赢得这场比赛吧！！

(科比照片一张)

假设总共比赛有m+1个人参加，告诉你科比和另外m个人的比赛的胜利可能性，你的任务就是求出在科比赢了的所有比赛的可能性最大的前提下(误差不超过1e-10)，科必打赢的人的最大能力值的和是多少？当然当一个人被你打败，他就不会再参加比赛了。

这里需要注意的是，科比能打赢其他人的可能性在不同场次是不同的。比如在比赛前期科比的手感不太好，对抗在内线称霸的人因为无法发挥外线的实力，而难以得分(接奥尼儿图一张)

中期时别人手感变好，状态起来，有实力的人会给科比制造很大的麻烦(接韦德图一张)

后期时消耗太多体力，对自己的命中率下降，难以发挥正常水平，所以对抗体力好的球员时占劣势(后接纳什图一张)

现在给你每场比赛科比对每个参赛者的获胜可能性，和每个人的能力值，帮助科比赢得比赛吧。

【输入格式】

第一行n,m(1<=n<<=10,n<=m<=100000),意义如题所述。

接下来一行m个整数表示其他m个人的能力值si(1<=si<=100)。

接下来是1个n*m的矩阵，描述在每场碰到每个人的获胜可能vij(0<=vij<=1)。

【输出格式】

第一行输出最大获胜可能性。

第二行输出最大能力值和。

【输入样例】

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