KND Factory

Problem

KND君は会津大学に在籍する学生プログラマである。彼の住む町の周辺には N 個の町がある。彼は生クリームが大好きなので毎日生クリームを食べるためにある町に工場を建設した。その工場では毎日 F リットルの生クリームが製造される。生クリームは運ぶたびに、移動元の町の気温と移動先の町の気温の絶対差だけ傷んでしまう。困ったことにこの近辺の町の気温は寒暖計によって計測できない。しかしながら調査によって、それぞれの町の気温を変数とした N 個の一次方程式からなる N 元一次連立方程式を導くことができた。あなたはこれを解くことによって各町の気温を知ることができる。また、ある町から他の町へ生クリームを運搬するにはパイプラインを用いる。パイプラインは一日に送ることのできる生クリームの量が限られている。一日に F リットルの生クリームを工場がある町 s からKND君が住む町 t へ生クリームをなるべく良い状態で送りたい。町には0から始まる番号がつけられているものとする。方程式の各項は高々ひとつの変数からなり定数項がひとつある。 F リットルの生クリームはどのような運び方をしても一日以内で任意の町へ送られる。

Input

入力は複数のテストケースからなる。ひとつのテストケースは以下の形式で与えられる。テストケースの数は入力として与えられる。

T
N s t F
a1,1 a1,2 ... a1,N c1
a2,1 a2,2 ... a2,N c2
...
aN,1 aN,2 ... aN,N cN
M1
d1,1 d1,2 ... d1,M1
f1,1 f1,2 ... f1,M1
M2
d2,1 d2,2 ... d2,M2
f2,1 f2,2 ... f2,M2
...
MN
dN,1 dN,2 ... dN,M2
fN,1 fN,2 ... fN,M2

ここで、

• T:テストケースの数
• N:町の数
• s:工場のある町
• t:KND君の住む町
• F:一日に作られる生クリームの量
• a_i,j:連立方程式の未知数としてのi番目の方程式中でj番目の町の気温にかかる係数。もしa_i,j=0ならj番目の町の気温はこの方程式に現れないことになる。以下の例も参照してほしい。
• c_i:i番目の方程式の定数項
• M_i:i番目の町が持っている生クリームを移動させる機械の数
• d_i,j:i番目の町が持っているj番目の機械が生クリームを移動させる先の町
• f_i,j:i番目の町が持っているj番目の機械が生クリームを1日に移動させられるリットル量

である。

N元一次連立方程式を表す行列の入力例:

 a +  b      = 6       1  1 0  6
3a + 2b + c  = 10  =>  3  2 1 10
 a - 2b + 3c = 6       1 -2 3  6

a,b,cが町0,1,2の気温を表す。

Constraints

入力は以下の条件を満たす。

• 入力はすべて整数。
• 0 < T ≤ 40
• 2 < N ≤ 100
• 0 ≤ s < N
• 0 ≤ t < N
• s ≠ t
• 0 < F ≤ 1000
• 0 ≤ M_i ≤ N
• -1000 ≤ a_i,j ≤ 1000
• 0 ≤f_i,j< 1000
• それぞれの町の気温は一意に定まる。

Output

各テストケースにつき、一日に F リットルの生クリームを工場がある町 s からKND君が住む町 t に運んだとき、生クリームの傷みの和を最小化した値を一行で出力せよ。この値はジャッジ出力の値と10^-5より大きい差を持ってはならない。また、町 s から町 t へ F リットルの生クリームを一日に運べない場合はimpossibleを一行で出力せよ。

Sample Input

3
3 0 2 5
1 1 1 6
3 2 1 10
1 -2 3 6
2
1 2
3 3
1
2
3
0
3 0 2 5
1 1 1 6
3 2 1 10
1 -2 3 6
2
1 2
2 2
1
2
2
0
10 2 7 20
8 9 -5 6 -9 5 1 0 4 9 4
3 -1 -8 0 -5 4 3 0 -3 2 4
-4 5 8 -4 1 -8 -6 3 3 5 -7
-7 0 2 5 8 -5 -9 -8 1 -2 -1
3 8 1 -3 8 2 -5 8 -3 4 -4
-2 5 0 -2 -4 4 -3 9 6 -1 -2
4 1 2 -9 3 5 6 -4 4 -1 -4
-4 6 6 9 -2 1 -9 -3 -7 3 -4
1 -1 6 3 1 -5 9 5 -5 -9 -5
-7 4 6 8 8 4 -4 4 -7 -8 -5
5
1 5 0 6 3
15 17 14 7 15
3
1 5 7
6 8 14
10
3 5 3 5 9 5 9 5 1 4
12 6 16 11 16 7 9 3 13 13
10
9 1 5 6 2 5 8 5 9 4
15 8 8 14 13 13 18 1 12 11
5
3 5 0 4 6
14 15 4 14 11
9
5 0 6 2 7 8 8 6 6
6 5 7 17 17 17 17 19 3
9
7 7 2 7 8 4 7 7 0
4 13 16 10 19 17 19 12 19
3
1 5 1
3 7 16
8
5 7 4 9 1 4 6 8
4 3 6 12 6 19 10 1
4
1 3 6 3
5 15 18 14

Sample Output

10.0000000000
impossible
11.9354380207

---