#P3769. Baseball on the Mercury

Baseball on the Mercury

Description

Baseball on the Mercury is similar to that on the Earth. This game is played between two teams: the batting team and the fielding team. There are four bases: home base, first base, second base and third base. They form a square called the baseball diamond. The players in the batting team bat the ball at home base one by one. Each of them bats exactly once.

The game starts with the first player of the batting team standing at home base, bats the ball. The other players of batting team wait outside. After that, the first player runs from base to base in the order of home base -> first base -> second base -> third base -> home base. He may stop at one of these bases, but he cannot stay still. If he reaches the home base again, he will leave the game and earn 1 point for his team.

Then the second player bats the ball at home base. After that, both players run in the same order mentioned above (If the first player has already left the game, the second player runs alone). The other players still wait outside. The second player may stop at one of these bases, but he cannot stay still. If one of them reaches the home base again, he will leave the game and earn 1 point for his team. If both of them do so, both leave and 2 points will be earned. And then the third player, the fourth player ... the Nth player of batting team bats the ball the same way. Notice that at any time, there should be at most 1 player at first base, at most 1 player at second base and at most 1 player at third base.

There are two ways of batting, ordinary way and sacrifice way. A player bats the ball in an ordinary way if and only if there was nobody at the third base before he bats. In an ordinary strategy, if the player bats unsuccessfully, he will get an "Out" and leave the game, and all other players must stay still. If the player bats successfully, the batting levels are shown below:

  1. The player bats bad. All other players who are at the bases and the batter can only run to the next base or stay still.
  2. The player bats good. All other players who are at the bases and the batter can run to one of the next 2 bases or stay still.
  3. The player bats very well. All other players who are at the bases and the batter can run to the one of the next 3 bases or stay still.
  4. The player bats excellent. All other players who are at the bases and the batter can run to one of the next 4 bases or stay still.

A player bats the ball in a sacrifice way if and only if there was somebody at the third base before he bats. In this case, he will get an "Out" after he bats, and he must leave the game. However, if he bats successfully, the other players who are at bases can run to one of the next 2 bases or stay still.

The score of the batting team is the points they get by returning to the home base minus the number of "Out" they get. Suppose that you are the coach of the batting team and you know your team-members very well -- you know the rate of every batting level and you can decide the strategy when they run from base to base, it means that you can decide which base they will stop at. But you cannot decide the order of players. You are so clever that you will make the expectation score of your team as high as possible. So what's the expectation score?

Input

There are several cases in the input file, end by 0. For each case,
The first line is an integer N (N<=10000), the number of players in your team.
Then followed N lines, each line describes the rates of a batter, in the bat order.
For each line, there are 5 real numbers, the rate of “bad bat”, the rate of “good bat”, the rate of “very well bat”, the rate of “excellent bat” and the rate of successful batting in the sacrifice way.
The input is always valid.

Output

For each case, the output contains 1 line, the expectation score. The answer should be rounded to 3 digits.

7
0.004 0.769 0.028 0.049 0.885
0.180 0.686 0.031 0.005 0.061
0.585 0.336 0.009 0.002 0.054
0.592 0.365 0.027 0.005 0.468
0.098 0.171 0.121 0.361 0.846
0.132 0.771 0.022 0.073 0.228
0.245 0.045 0.060 0.559 0.691
0
3.700

Source