Problem Description

There are $n$ contestants participating in the show “Open the Door and Win Big”. There are $m$ sets of questions. Each set contains $p$ questions. The probability that contestant $i$ answers question $k$ in set $j$ correctly is $f_{i,j,k}$. If a contestant answers any question wrong, their answering process ends immediately.

If a contestant answers question $i$ correctly, they receive an additional reward of $c_i$ yuan on top of the rewards already obtained. Contestants always start from the first question and answer in order.

At the same time, to prevent too many contestants from doing the same set, there are also $y$ constraints of the form: “the set index of contestant $i$ must be at least $k$ larger than that of contestant $j$”.

You need to assign one set of questions to each contestant (different contestants may be assigned the same set), so that the sum of everyone’s expected rewards is minimized.

Input Format

The input contains multiple test cases. The first line is an integer $T$, the number of test cases.

For each test case, the first line contains four integers $n,m,p,y$.

The next line contains $p$ integers, where the $i$-th one is $c_i$.

Then follow $m$ matrices of size $n\times p$. In the $j$-th matrix, the real number in row $i$ and column $k$ is $f_{i,j,k}$.

Then follow $y$ lines, each containing three integers $i,j,k$ ($1\le i,j\le n$, $-m<k<m$), describing one constraint.

Output Format

For each test case, output one real number, the answer. If there is no solution, output -1.

This problem uses a Special Judge. Any answer with an error within $5\times 10^{-4}$ is accepted.

Because the SPJ is sensitive, please output a newline at the end of each test case, and do not output any other characters.

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

Hint

[Sample Explanation]

Only the second test case is explained here.

There are only two sets of questions, and the set index of the second person is larger than that of the third person. Therefore, the second person must choose the second set, and the third person chooses the first set.

If the second person chooses the second set, the expected cost is: $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$.

The calculation method for other people is similar.

[Constraints]

This problem uses bundled testdata.

For all data, $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$. It is guaranteed that the input size of each test point is less than $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$.

Translated by ChatGPT 5