오락실!

오락실에 가 본 적이 있는가? 오락실 게임은 해가 갈수록 실력이 덜 필요한 쪽으로 바뀌었고, 요즘 나오는 기계는 결과가 거의 운으로 갈린다. 그림에 있는 기계를 보자. 구멍이 삼각형 모양으로 배치되어 있다. 구슬은 맨 위 구멍 근처에 떨어진다. 구슬은 그 구멍으로 빠져서 게임이 끝나거나, 빨간 화살표가 가리키는 이웃 구멍(최대 4개) 중 하나로 튄다. 구멍마다 배당이 다르고, 배당이 음수인 구멍도 있다. 구슬이 다른 구멍에 닿으면 같은 과정을 반복한다. 그 구멍으로 빠져서 게임이 끝나거나, 다시 이웃으로 튄다. 이 과정은 끝없이 이어질 수도 있다.

구슬을 한 번 넣었을 때 배당의 기댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 기계의 줄 수 $N$이 주어진다 ($1 \le N \le 32$).

둘째 줄에 $H = N(N+1)/2$개의 정수 $v_1, v_2, \dots, v_H$가 주어진다 ($-100 \le v_i \le 100$). $v_i$는 구슬이 $i$번 구멍으로 빠졌을 때 받는 배당이고, 음수일 수 있다. 구멍 번호는 위에서 아래로 매긴다. 첫째 줄에 1번 구멍이 있고, 둘째 줄에 2번과 3번 구멍이 있다. $k$번째 줄은 $k(k-1)/2 + 1$번 구멍으로 시작하고 구멍이 정확히 $k$개 있다.

그 다음 $H$개의 줄에는 각각 실수 다섯 개 p0 p1 p2 p3 p4가 주어진다. $i$번째 줄은 $i$번 구멍에서 구슬이 왼쪽 위 이웃으로 튈 확률 p0, 오른쪽 위 이웃으로 튈 확률 p1, 왼쪽 아래 이웃으로 튈 확률 p2, 오른쪽 아래 이웃으로 튈 확률 p3, 그 구멍으로 빠질 확률 p4를 나타낸다. 각 확률은 소수점 아래 최대 3자리까지 주어지고, $0.0 \le p_i \le 1.0$이며 다섯 값의 합은 정확히 $1.0$이다.

$k$번째 줄의 $c$번째 구멍을 기준으로 이웃은 다음과 같다. 왼쪽 위 이웃은 $k-1$번째 줄의 $c-1$번째 구멍, 오른쪽 위 이웃은 $k-1$번째 줄의 $c$번째 구멍, 왼쪽 아래 이웃은 $k+1$번째 줄의 $c$번째 구멍, 오른쪽 아래 이웃은 $k+1$번째 줄의 $c+1$번째 구멍이다. 기계의 가장자리라서 없는 이웃으로 튈 확률은 항상 $0.0$으로 주어진다. 예를 들어 1번 구멍은 위쪽 이웃이 없으므로 p0과 p1이 모두 $0.0$이다.

구슬이 $b$번 튄 뒤에도 아직 어느 구멍에도 빠지지 않았을 확률은 최대 $(1 - 10^{-3})^{\lfloor b/H \rfloor}$라고 가정해도 된다.

게임 한 판의 배당 기댓값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 자리는 반드시 여섯 자리를 채워서 쓰고, 반올림한 값이 $0$이면 부호를 붙이지 말고 0.000000을 출력한다.

구슬을 여러 번 굴려서 어느 구멍에 빠지는지 난수로 흉내내는 몬테카를로 방식으로는 이 정확도가 나오지 않는다.