T-shirt

5000ms

262144K

Description:

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.

Input:

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.

Output:

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.

Sample Input:

2 2
500 500
500 500

Sample Output:

1.500000000000

Sample Input:

Sample Output:

3.000000000000

Sample Input:

1 4
100 200 300 400

Sample Output:

0.400000000000

Note:

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.

Informação

Provedor Codeforces

Código CF183D