← 返回题目列表

Codeforces · 183/D

D. T 恤

中文机器翻译题面 查看原题

您将作为实习生在 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 恤。