您将作为实习生在 Codeforces 的 n 个工程师团队中工作,编号为 1 到 n。您想给每位工程师一件纪念品:一件来自您所在国家/地区的 T 恤(T 恤在 Codeforces 中非常受欢迎)。不幸的是,您不知道每个工程师适合穿的 T 恤尺寸。有 m 种不同的尺寸,编号为 1 到 m,每个工程师都适合穿同一种尺寸的 T 恤。
您不知道工程师的确切尺寸,因此您询问了您的朋友 Gerald。不幸的是,他也无法获得确切的尺寸,但他设法获得了每个工程师 i 和所有尺寸 j 的 T 恤尺寸适合工程师 i 的概率为 j。
由于您计划为每位工程师提供一件 T 恤,因此您将携带恰好 n 件 T 恤。对于这 n 件 T 恤,您可以携带任意尺码组合(您也可以携带多件相同尺码的 T 恤!)。在决定携带什么尺码时,您不知道每个工程师的 T 恤尺码,因此您必须仅根据您的朋友 Gerald 给出的概率来选择此组合。
你的任务是最大限度地增加收到同尺寸 T 恤的工程师的预期数量。
更正式的定义如下。当你最终到达办公室时,你会询问每个工程师他的T恤尺寸。然后,如果你还有一件这个尺寸的T恤,你就给他一件。否则,你不会给他一件T恤。您将按照从工程师 1 开始,然后是工程师 2,依此类推,直到工程师 n 的顺序询问工程师。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 300),分别表示工程师的数量和 T 恤尺寸的数量。
接下来n行,每行包含m个空格分隔的整数。第 i 行中的第 j 个整数表示第 i 个工程师适合穿 j 号 T 恤的概率。每个概率将以 0 到 1000 之间的整数形式给出(含 0 和 1000)。实际概率应计算为给定数字除以 1000。
保证对于任何工程师来说,所有 m 件 T 恤的概率之和等于 1。
输出
打印一个实数,表示将收到 T 恤的工程师的最大可能预期数量。
对于答案,10 - 9 的绝对或相对误差是可以接受的。
示例
输入 #1
2 2 500 500 500 500
输出 #1
1.500000000000
输入 #2
3 3 1000 0 0 1000 0 0 0 1000 0
输出 #2
3.000000000000
输入 #3
1 4 100 200 300 400
输出 #3
0.400000000000
注意
对于第一个示例,请携带每种尺寸的一件 T 恤。如果有 0.5 的机会,则两个工程师要么都适合穿尺码 1 的 T 恤,要么都适合穿尺码 2 的 T 恤。如果有 0.5 的机会,一个工程师适合穿尺码 1 的 T 恤,另一个工程师穿尺码 2 的 T 恤。如果第一个为真,则收到 T 恤的工程师数量为 1。如果第二个为真,则此类工程师的数量为两名。因此,收到 T 恤的工程师的预期数量是 1.5。这是所有 T 恤套装的最大可能预期工程师数量。
第二个例子,带两件1码的T恤和一件2码的T恤。这样,每个工程师一定会收到一件他尺码的T恤。
对于第三个示例,请携带一件 4 号 T 恤。