Cady is done trying to act dumb! As the newest member of the North Shore High's Mathletes, she's up against Marymount High in the ICMT State Final Math Championships.

In the first round, the Mathletes will be asked ~n~ questions in a row. Any member of the Mathletes can attempt answer a question, but no member can attempt to answer a question twice in a row.

Ahead of time, the Mathletes have figured out how likely it is that each of them gets each question correct. If each member chooses to buzz in at the right times, what is the expected number of questions the Matheletes will get correct?

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 500)~, the number of Mathletes.

The next line consists of an integer ~m~ ~(1 \leq m \leq 500)~, the number of questions in the contest.

The next ~n~ lines contain a string ~S~ ~(1 \leq S.\text{length} \leq 10)~ and integers ~p_1, p_2, ..., p_m~ ~(0 \leq p_i \leq 1)~, indicating that member ~S~ has a ~p_1~ probability of getting the first question correct, a ~p_2~ probability of getting the second question correct, and so on. ~S~ can be any string of English characters.

Output

Output the expected number of questions that the Mathletes will get correct.

Clarifications

• Probabilities are given with up to ~4~ decimal places of precision.
• Your answer also be correct to ~4~ decimal places.

Example

Input

4
4
Tyler 0.5 0.4 0.8 0.1
Kevin 0.9 0.7 0.9 0.4
Tim 0.4 0.6 0.1 0.2
Cady 0.1 0.3 0.8 0.9

Output

3.3000

If the Mathletes buzz in optimally, then:

• Kevin should answer question ~1~, with a ~90\%~ chance of a correct answer.
• Tim should answer question ~2~, with a ~60\%~ chance of a correct answer.
• Kevin should answer question ~3~, with a ~90\%~ chance of a correct answer.
• Cady should answer question ~4~, with a ~90\%~ chance of a correct answer.

Overall, the team should expect to get ~3.3~ questions correct.