CF183D.T-shirt

You are going to work in Codeforces as an intern in a team of n engineers, numbered 1 through n. You want to give each engineer a souvenir: a T-shirt from your country (T-shirts are highly desirable in Codeforces). Unfortunately you don't know the size of the T-shirt each engineer fits in. There are m different sizes, numbered 1 through m, and each engineer will fit in a T-shirt of exactly one size.

You don't know the engineers' exact sizes, so you asked your friend, Gerald. Unfortunately, he wasn't able to obtain the exact sizes either, but he managed to obtain for each engineer i and for all sizes j, the probability that the size of the T-shirt that fits engineer i is j.

Since you're planning to give each engineer one T-shirt, you are going to bring with you exactly n T-shirts. For those n T-shirts, you can bring any combination of sizes (you can bring multiple T-shirts with the same size too!). You don't know the sizes of T-shirts for each engineer when deciding what sizes to bring, so you have to pick this combination based only on the probabilities given by your friend, Gerald.

Your task is to maximize the expected number of engineers that receive a T-shirt of his size.

This is defined more formally as follows. When you finally arrive at the office, you will ask each engineer his T-shirt size. Then, if you still have a T-shirt of that size, you will give him one of them. Otherwise, you don't give him a T-shirt. You will ask the engineers in order starting from engineer 1, then engineer 2, and so on until engineer n.

你将在 Codeforces 担任一名实习生，加入一支由 $n$ 名工程师组成的团队，工程师编号为 $1$ 至 $n$。你想为每位工程师赠送一件来自你国家的纪念 T 恤（T 恤在 Codeforces 社区中极为抢手）。不幸的是，你并不知道每位工程师适合的 T 恤尺码。一共有 $m$ 种不同尺码，编号为 $1$ 至 $m$，且每位工程师恰好只适合其中一种尺码。

你不知道各位工程师的确切尺码，于是向你的朋友 Gerald 打听。遗憾的是，Gerald 也未能获得确切尺码信息，但他成功获取了如下概率：对每位工程师 $i$ 及每种尺码 $j$，他给出了工程师 $i$ 适合尺码 $j$ 的概率。

由于你计划为每位工程师赠送一件 T 恤，因此你将携带恰好 $n$ 件 T 恤。对于这 $n$ 件 T 恤，你可以任意选择尺码组合（允许携带多件相同尺码的 T 恤！）。你在决定携带哪些尺码时，并不知道每位工程师的实际尺码，因此必须仅依据 Gerald 提供的概率信息来选定该尺码组合。

你的任务是最大化收到合身 T 恤的工程师人数的期望值。

其形式化定义如下：当你最终抵达办公室后，你将依次询问每位工程师的 T 恤尺码（按工程师 $1$、工程师 $2$、……、工程师 $n$ 的顺序）。若你此时仍有该尺码的 T 恤剩余，则立即赠送其一件；否则不赠送。

The first line contains two space-separated integers n and m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 300), denoting the number of engineers and the number of T-shirt sizes, respectively.

Then n lines follow, each line contains m space-separated integers. The j-th integer in the i-th line represents the probability that the i-th engineer fits in a T-shirt of size j. Each probability will be given as an integer between 0 and 1000, inclusive. The actual probability should be calculated as the given number divided by 1000.

It is guaranteed that for any engineer, the sum of the probabilities for all m T-shirts is equal to one.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n \leq 3000$，$1 \leq m \leq 300$），分别表示工程师人数和 T 恤尺码种类数。

接下来有 $n$ 行，每行包含 $m$ 个以空格分隔的整数。第 $i$ 行中的第 $j$ 个整数表示第 $i$ 位工程师适合第 $j$ 种尺码 T 恤的概率。每个概率以 $0$ 到 $1000$（含）之间的整数给出；实际概率应通过将该整数除以 $1000$ 计算得到。

保证对任意一位工程师，其对应的所有 $m$ 种尺码 T 恤的概率之和等于 $1$。

Print a single real number denoting the maximum possible expected number of engineers that will receive a T-shirt.

For the answer the absolute or relative error of 10 - 9 is acceptable.

输出一个实数，表示可能获得T恤的工程师人数的最大期望值。

答案的绝对或相对误差在 $10^{-9}$ 范围内均可接受。

For the first example, bring one T-shirt of each size. With 0.5 chance, either both engineers fit inside T-shirts of size 1 or both fit inside T-shirts of size 2. With the other 0.5 chance, one engineer fits inside a T-shirt of size 1 and the other inside a T-shirt of size 2. If the first is true, the number of engineers that receive a T-shirt is one. If the second is true, the number of such engineers is two. Hence, the expected number of engineers who receive a T-shirt is 1.5. This is maximum possible expected number of engineers for all sets of T-shirts.

For the second example, bring two T-shirts of size 1 and one T-shirt of size 2. This way, each engineer will definitely receive a T-shirt of his size.

For the third example, bring one T-shirt of size 4.

对于第一个样例，每种尺码各准备一件T恤。有 $0.5$ 的概率，两名工程师均能穿上尺码为 $1$ 的T恤，或均能穿上尺码为 $2$ 的T恤；另有 $0.5$ 的概率，一名工程师能穿上尺码为 $1$ 的T恤，另一名则能穿上尺码为 $2$ 的T恤。若前一情况成立，则收到T恤的工程师人数为 $1$；若后一情况成立，则收到T恤的工程师人数为 $2$。因此，收到T恤的工程师人数的期望值为 $1.5$。这是所有可能的T恤组合中所能达到的最大期望值。

对于第二个样例，准备两件尺码为 $1$ 的T恤和一件尺码为 $2$ 的T恤。这样，每名工程师都必定能收到符合其尺码的T恤。

对于第三个样例，准备一件尺码为 $4$ 的T恤。