Minimizing Expected Rewards in the Game Show

In the game show Open the Door for Luck, there are (n) contestants and (m) sets of questions. Each set contains (p) questions. The probability that contestant (i) correctly answers the (k)th question in set (j) is given by (f_{i,j,k}). Contestants answer the questions in order starting from the first question and stop at the first wrong answer. When a contestant correctly answers the (i)th question, they earn an additional reward of (c_i) (added on top of previously accumulated rewards). Thus, if contestant (i) is assigned set (j), the expected reward is computed as: [ E_{i,j} = \sum_{k=1}^{p} c_k \prod_{h=1}^{k} f_{i,j,h}. ]

Additionally, there are (y) constraints provided to prevent too many contestants from choosing the same set. Each constraint is of the form: "The set number for contestant (u) must be at least (k) greater than that for contestant (v)"; in other words, if (x_i) denotes the assigned set number for contestant (i), then each constraint is given by: [ x_u \ge x_v + k. ]

Your task is to assign each contestant a set (the same set may be assigned to different contestants) such that the sum of the expected rewards of all contestants is minimized. You are to output the minimum possible total expected reward.

Input Format:

• The first line contains four integers: \(n\), \(m\), \(p\) and \(y\) — the number of contestants, the number of question sets, the number of questions per set, and the number of constraints, respectively.
• Then follow \(n \times m\) lines. For each contestant \(i\) (\(1 \le i \le n\)) and for each set \(j\) (\(1 \le j \le m\)), there is a line containing \(p\) real numbers. The \(k\)th number on this line is \(f_{i,j,k}\), the probability that contestant \(i\) answers the \(k\)th question correctly when given set \(j\).
• The next line contains \(p\) real numbers: \(c_1, c_2, \dots, c_p\) — the rewards for each correctly answered question.
• Then follow \(y\) lines, each containing three integers \(u\), \(v\) and \(d\), representing the constraint: \(x_u \ge x_v + d\), where \(x_i\) is the set number assigned to contestant \(i\) (1-indexed).

Output Format:

• Output a single real number — the minimum total expected reward achievable under the given constraints. It is guaranteed that there is at least one valid assignment.

Note:

• You may assume that \(n\) and \(m\) are small enough that a brute-force or backtracking solution will pass.
• Please make sure that your formulas are written in \(\LaTeX\) format as above.

inputFormat

The input begins with four integers \(n\), \(m\), \(p\), and \(y\). Then for each contestant \(i\) (1-indexed), and for each set \(j\) (1-indexed), there is a line with \(p\) floating-point numbers representing \(f_{i,j,1}, f_{i,j,2}, \ldots, f_{i,j,p}\). Following these \(n \times m\) lines is a single line with \(p\) integers/floats \(c_1, c_2, \ldots, c_p\). Finally, there are \(y\) lines each containing three integers \(u\), \(v\), and \(d\), indicating the constraint \(x_u \ge x_v + d\).

Sample Input:

3 3 2 2
0.8 0.5
0.6 0.6
0.9 0.3
0.7 0.4
0.8 0.8
0.5 0.9
0.6 0.6
0.7 0.5
0.8 0.4
100 50
1 2 1
3 1 1

outputFormat

Output a single real number which is the minimum sum of expected rewards over all contestants. For the sample input above, the correct output is:

258

sample

3 3 2 2
0.8 0.5
0.6 0.6
0.9 0.3
0.7 0.4
0.8 0.8
0.5 0.9
0.6 0.6
0.7 0.5
0.8 0.4
100 50
1 2 1
3 1 1

258