题目描述

$n$ 位选手去参加节目“开门大吉”。共有 $m$ 套题，每套题包含 $p$ 个题目，第 $i$ 位选手答对第 $j$ 套题中第 $k$ 道的概率为 $f_{i,j,k}$。

若一位选手答对第 $i$ 题，会在已得到奖励的基础上，再得到 $c_i$ 元奖励。选手总是从第一道开始，按顺序答题的。

同时，为了防止过多的选手做同一套题，还有 $y$ 条形如“第 $i$ 位选手的套题编号必须至少比第 $j$ 位的大 $k$”的限制。

你需要给每一位选手分配一套题（不同选手可以相同），使得所有人的期望奖励和最小。

输入格式

输入包含多组数据。第一行是一个整数 $T$，为数据组数。

对于每组数据，第一行四个整数 $n,m,p,y$。

接下来一行 $p$ 个整数，第 $i$ 个为 $c_i$。

接下来 $m$ 个 $n\times p$ 的矩阵，第 $j$ 个矩阵中第 $i$ 行第 $k$ 个实数为 $f_{i,j,k}$。

接下来 $y$ 行，每行三个整数 $i,j,k$（$1\le i,j\le n$，$-m\lt k\lt m$），描述一条限制。

输出格式

对于每组数据，输出一个实数，为答案。无解输出 -1。

本题有 Special Judge，答案误差在 $5\times 10^{-4}$ 以内都算对。

由于 SPJ 敏感，请在每组数据末尾都输出一个换行符，并不要再输出其它字符。

样例

输入

4
3 2 4 0
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
3 2 4 1
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
2 3 1
3 2 4 1
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
1 2 1
3 2 4 2
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
1 2 1
2 3 1

输出

15.1460
18.5340
18.7560
-1

数据范围与样例解释

【样例解释】

这里只解释第二组数据。

一共只有两套题，而第二个人的套题编号大于第三个人，因此第二个人一定是选第二套，第三个人选第一套。

第二个人选第二套，期望支出：$0.2\times (1-0.5)\times 10+0.2\times 0.5 \times (1-0.3) \times 20+0.2\times 0.5 \times 0.3\times (1-0.6) \times 30+0.2\times 0.5 \times 0.3\times 0.6 \times 50=3.66$。

其他人的计算方法类似。

【数据范围】

本题捆绑测试。

对于所有数据，$1\le n,m,p\le 80$，$0\le y\le 10^3$，$0\le f_{i,j,k} \le 1$，$0\le c_i\le 10^5$，$1 \le T\le 50$。保证每个测试点的输入数据大小小于 $10\text{MB}$。

Subtask 1（20 pts）：$n,m,p,y\le 7$；

Subtask 2（20 pts）：$T\le 6$，$y=0$；

Subtask 3（20 pts）：$n,m,p\le 30$，$y\le 200$；

Subtask 4（20 pts）：$T=1$；

Subtask 5（20 pts）：$T\le 5$。