Arcade!

Have you been to an arcade lately? Arcade games have needed less and less skill over the years, and the machines you find today decide almost everything by luck. Look at the machine in the picture. Its holes are arranged in a triangle. A ball is dropped near the hole at the top. The ball either falls into that hole, which ends the game, or it bounces to one of the neighboring holes marked by the red arrows (up to 4 of them). Every hole has its own payout, and some payouts are negative. When the ball reaches another hole, the same thing happens again. It either falls in and ends the game, or it bounces to a neighbor. The bouncing can go on forever.

Write a program that computes the expected payout of dropping one ball into the machine.

The first line contains the number of rows $N$ of the machine ($1 \le N \le 32$).

The second line contains $H = N(N+1)/2$ integers $v_1, v_2, \dots, v_H$ ($-100 \le v_i \le 100$), where $v_i$ is the payout the player receives if the ball falls into hole $i$. A payout may be negative. Holes are numbered from top to bottom. Row 1 holds hole 1, row 2 holds holes 2 and 3, and row $k$ starts with hole $k(k-1)/2 + 1$ and holds exactly $k$ holes.

The next $H$ lines each contain five real numbers p0 p1 p2 p3 p4. Line $i$ gives, for hole $i$, the probability that the ball bounces to its top-left neighbor (p0), to its top-right neighbor (p1), to its bottom-left neighbor (p2), to its bottom-right neighbor (p3), and the probability that the ball falls into the hole (p4). Each probability is given with at most 3 digits after the decimal point, $0.0 \le p_i \le 1.0$, and the five values sum to exactly $1.0$.

For the hole in position $c$ of row $k$, the top-left neighbor is hole $c-1$ of row $k-1$, the top-right neighbor is hole $c$ of row $k-1$, the bottom-left neighbor is hole $c$ of row $k+1$, and the bottom-right neighbor is hole $c+1$ of row $k+1$. When a hole sits on the boundary and a neighbor does not exist, the probability of bouncing there is always given as $0.0$. Hole 1, for instance, has no hole above it, so p0 and p1 are both $0.0$.

You can assume that after the ball has bounced $b$ times, the probability that it has not yet fallen into any hole is at most $(1 - 10^{-3})^{\lfloor b/H \rfloor}$.

Print the expected payout of one game on a single line, rounded to six digits after the decimal point. Always write all six digits, and when the rounded value is $0$, print 0.000000 with no sign.

A Monte Carlo approach, dropping many balls and picking each bounce at random, does not reach this accuracy.