Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. T-shirt

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

2 2

500 500

500 500

Output

1.500000000000

Input

3 3

1000 0 0

1000 0 0

0 1000 0

Output

3.000000000000

Input

1 4

100 200 300 400

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/26/2020 23:11:41 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|