토벤머리 용사의 스타포스 강화

토벤머리 용사는 자신이 가장 아끼는 장비 아이템의 스타포스를 강화하던 중 가장 효과적으로 스타포스를 진행하는 방법이 궁금해졌다.

아이템은 $0$ 이상 $N$ 이하의 정수 값 레벨을 갖는다. 아이템의 초기 레벨은 $0$이다.

이제 스타포스 강화의 진행 과정을 살펴보자. 레벨 $i$ ($0 \le i \le N - 1$)의 아이템을 강화하기 위해서는 먼저 $C_i$의 비용을 지불해야 한다. 이후에는 다음 중 하나의 이벤트가 랜덤하게 발생한다:

• 각 $0 \le j \le i - 1$에 대해, $P_{i,\, j}$의 확률로 강화에 실패하여 레벨이 $i$에서 $j$로 감소한다.
• 각 $i + 1 \le j \le N$에 대해, $P_{i,\, j}$의 확률로 강화에 성공하여 레벨이 $i$에서 $j$로 증가한다.

편의상, $P_{i,\, i} = 0$이라고 하자. $P_{i,\, 0} + P_{i,\, 1} + \cdots + P_{i,\, N} = 1$이다. 즉, 강화 시에는 위의 $N$가지 이벤트 중 정확히 하나의 이벤트가 발생한다.

강화를 시도하기 직전마다 최대 한 개의 하락 방지 쿠폰을 구입할 수 있는데, 이 쿠폰은 사용 직후의 강화에만 적용된다. 레벨 $i$ ($1 \le i \le N - 1$)의 아이템을 강화하기 직전 구입할 수 있는 쿠폰은 다음과 같이 $i$가지가 있다:

• 각 $0 \le j \le i - 1$에 대해, $D_{i,\, j}$의 비용을 지불하여 $i \rightarrow j$ 하락 방지 쿠폰을 구입할 수 있다. 이 쿠폰은 강화에 실패하여 레벨이 $k$로 감소하는 이벤트가 발생할 경우, 아이템의 레벨을 $\max (k, j + 1)$로 바꾼다. 즉, 강화에 실패하더라도 레벨이 $j$ 이하가 되지 않도록 보장해 준다.

강화 비용과 강화 이벤트의 확률, 쿠폰의 비용, 그리고 목표 레벨 $N$이 주어질 때, 최적의 전략을 사용하여 레벨 $0$의 아이템을 레벨 $N$으로 강화하기 위한 비용의 기댓값의 최솟값을 구하시오.

입력 형식

첫 줄에 테스트 케이스의 수를 나타내는 양의 정수 $T$가 주어진다. 그다음 줄부터 각 테스트 케이스에 대한 정보가 주어진다.

• 각 테스트 케이스의 첫 줄에 최대 레벨을 나타내는 정수 $N$이 주어진다.
• 그다음 줄에 강화 비용을 나타내는 $N$개의 정수 $C_0, C_1, \cdots, C_{N - 1}$이 공백으로 구분되어 차례대로 주어진다.
• 이어지는 $N - 1$개의 줄의 $i$ ($1 \le i \le N - 1$)번째 줄에는 레벨 $i$의 강화에서 구입할 수 있는 하락 방지 쿠폰의 가격을 나타내는 $i$개의 정수 $D_{i,\, 0}, D_{i,\, 1}, \cdots, D_{i,\, i - 1}$이 공백으로 구분되어 차례대로 주어진다.
• 이어지는 $N$개의 줄의 $i + 1$ ($0 \le i \le N - 1$)번째 줄에는 레벨 $i$의 강화에서 발생하는 이벤트의 확률의 $1\,000\,000$ 배의 값을 나타내는 $N + 1$개의 정수 $(1\,000\,000 \times P_{i,\, 0}), (1\,000\,000 \times P_{i,\, 1}), \cdots, (1\,000\,000 \times P_{i,\, N})$이 공백으로 구분되어 차례대로 주어진다.

입력 제한

각 테스트 케이스에서의 $N$은 $1$ 이상 $15$ 이하이며, 모든 테스트 케이스에서의 $N$의 합은 $100$ 이하이다.

각 테스트 케이스 안에서 모든 $0$ 이상 $N-1$ 이하인 $i$에 대해,

• $1 \le C_{0} \le C_1 \le \cdots \le C_{N-1} \le 1\,000\,000$
• $1 \le D_{i,\, 0} \le D_{i,\, 1} \le \cdots \le D_{i,\, i - 1} \le 1\,000\,000$
• $P_{i,\, i} = 0$
• $P_{i,\, 0} + P_{i,\, 1} + \cdots + P_{i,\, N} = 1$
• $P_{i,\, 0} \le P_{i,\, 1} \le \cdots \le P_{i,\, i - 1}$
• $P_{i,\, i + 1} \ge P_{i,\, i + 2} \ge \cdots \ge P_{i,\, N}$
• $\dfrac{1}{3} \le P_{i,\, i + 1}$

을 만족한다.

출력 형식

각 테스트 케이스마다 한 줄에 하나씩 레벨 $0$의 장비 아이템을 레벨 $N$으로 강화하기 위한 비용의 기댓값의 최솟값을 출력한다.

정답과 상대 오차가 $10^{-4}$ 이하라면 정답으로 인정된다.

예제 1

1
1
3
0 1000000

3

예제 2

2
2
8 11
4
0 990000 10000
660000 0 340000
2
8 11
5
0 990000 10000
660000 0 340000

51.6764705882
54.5008655511

예제 3

1
3
291 447 992
8703
250915 310205
0 1000000 0 0
287837 0 712163 0
103122 367022 0 529856

3626.412107746

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설