햄릿

대학 1학년을 마치고 집에 돌아왔더니 아버지가 세상을 떠났고, 아버지의 동생인 삼촌이 어머니와 결혼해 있다. 얼마 지나지 않아 아버지의 유령이 나타나 삼촌이 자신을 죽였다고 말한다. 게다가 당신은 덴마크의 왕자이고, 삼촌은 새 왕이다. 희곡 햄릿은 이렇게 시작한다. 햄릿은 크게 흔들리고, 유명한 독백에서 생각을 정리한다.

To be, or not to be: that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune
Or to take arms against a sea of troubles
And by opposing end them. [...]

햄릿은 자살까지 포함해 자기가 고를 수 있는 행동을 하나씩 저울질한다. 어느 쪽이든 결과는 불확실하다. 깊이 잠들 수도 있고(좋은 결말), 죽음 속에서 악몽에 시달릴 수도 있다(나쁜 결말). 뒤에 어머니와 이야기하다가 커튼 뒤에서 소리가 나자, 누가 있는지 모르는 채로 커튼을 찌른다. 삼촌이었다면 이야기는 잘 끝났을지도 모른다. 그러나 거기 있던 사람은 햄릿이 사랑하는 여인의 아버지였고, 그 여인은 물에 빠져 죽는다. 햄릿은 결과를 알 수 없는 행동을 여러 번 골라야 한다. 덴마크 왕가가 모두 죽는 결말을 피하도록 햄릿의 선택을 도와라.

줄거리가 놓일 수 있는 상태가 주어진다. "시작", "햄릿이 스스로 목숨을 끊고 편히 잠들었다", "햄릿이 스스로 목숨을 끊고 지옥에서 고통받는다", "햄릿이 삼촌 클로디어스를 찔렀다", "햄릿이 폴로니어스를 찌르고 오필리아가 물에 빠져 죽었다" 같은 것이다. 어떤 상태는 이야기의 결말이고, 그런 상태에는 값이 하나 붙어 있다. 결말이 아니면 햄릿이 고를 수 있는 행동이 하나 이상 있고, 각 행동마다 그 행동의 결과로 이어질 수 있는 상태의 확률분포가 주어진다. 커튼 뒤의 사람을 찌르면 확률 0.4로 클로디어스, 0.5로 폴로니어스, 0.1로 하인일 수 있고, 그에 따라 서로 다른 세 상태로 이어진다.

줄거리에는 순환이 없다. 상태에는 1부터 $n$까지 번호가 붙어 있고, 모든 행동은 번호가 같거나 더 작은 상태로 넘어갈 확률이 0이다. 이야기는 상태 1에서 시작한다.

계산이 어떻게 되는지 예를 들어 보자. 햄릿이 커튼을 찌를지 말지 고를 수 있다고 하자. 커튼 뒤에 클로디어스가 있으면 줄거리는 값 3으로 끝난다. 하인이 있으면 값 -1로 끝난다. 폴로니어스가 있으면 오필리아가 물에 빠져 죽고, 레어티즈가 몰래 독을 바른 검으로 결투를 신청한다. 햄릿이 결투를 받아들이면 둘 다 죽고 값은 -10이다. 거절하면 확률 0.5로 독이 든 포도주 때문에 둘 다 죽고, 나머지 경우에는 둘 다 살지만 폴로니어스와 오필리아는 죽은 채로 남아 값이 -5다. 거절하는 쪽의 값이 $0.5 \times (-10) + 0.5 \times (-5) = -7.5$이므로, 커튼을 찌르는 행동의 값은 $0.4 \times 3 + 0.1 \times (-1) + 0.5 \times (-7.5) = -2.65$이다. 이 값을 커튼을 찌르지 않는 행동의 값과 같은 방식으로 계산해 비교하면 된다.

햄릿이 도달하는 모든 상태에서 가장 좋은 행동을 골랐을 때 상태 1에서 얻을 수 있는 기댓값의 최댓값을 출력하여라.

첫 줄에 입력에 들어 있는 데이터 집합의 개수 $K$ ($K \ge 1$)가 주어진다. 이어서 $K$개의 데이터 집합이 주어진다.

각 데이터 집합의 첫 줄에는 줄거리 상태의 개수 $n$ ($1 \le n \le 1000$)이 주어진다.

그다음 상태 $i = 1$부터 $n$까지 차례로 $n$개의 상태 설명이 주어진다. 상태 $i$ 설명의 첫 줄에는 상태 $i$에서 햄릿이 고를 수 있는 행동의 개수 $a_i$ ($0 \le a_i \le 5$)가 주어진다.

$a_i = 0$이면 다음 줄에 결말 $i$의 값인 실수 $v_i \in [-1000, 1000]$이 주어진다.

$a_i > 0$이면 $a_i$개의 줄이 이어진다. $k$번째 줄에는 실수 $p^{(k)}_{i,1}, \ldots, p^{(k)}_{i,n}$이 주어지고, $p^{(k)}_{i,j} \in [0, 1]$이며 $\sum_j p^{(k)}_{i,j} = 1$이다. 이 값은 햄릿이 상태 $i$에서 행동 $k$를 골랐을 때 상태 $i$에서 상태 $j$로 넘어갈 확률이다. $i \ge j$인 모든 $p^{(k)}_{i,j}$는 0이고, 따라서 상태 $n$은 항상 결말이며 $a_n = 0$이다.

각 데이터 집합의 정답은 소수점 둘째 자리로 반올림할 때 경계가 되는 값에서 $10^{-6}$ 이상 떨어져 있다. 아래의 반올림에 모호함이 생기지 않는다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 1부터 세는 데이터 집합의 번호다. 다음 줄에는 햄릿이 확보할 수 있는 기댓값의 최댓값을 소수점 둘째 자리까지 반올림해 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다. 반올림한 값이 0이면 -0.00이 아니라 0.00을 출력한다.