Assume you are Li Hua.
As an excellent liberal arts student, you have recently been studying electricity.
You have $\infty$ point charges, each with a charge of $+e$ and sufficient kinetic energy. You need to feed some of them into a machine and extract an equal number of point charges. Maximize the sum of the kinetic energy of the charges after the machine operates.
The machine can be viewed as $n$ nodes, where the $i$-th node has an electric potential of $h_i \,\mathrm{V}$.
At the $i$-th node, there are $p_i$ pipes through which a point charge can be fed into the node. Each pipe can be used to feed at most one point charge throughout the entire process. A point charge fed through the $j$-th pipe at node $i$ will do $a_{i,j} \,\mathrm{eV}$ of work against external forces.
At the $i$-th node, there are $q_i$ pipes through which a point charge can be extracted from the node. Each pipe can be used to extract at most one point charge throughout the entire process. A point charge extracted through the $j$-th pipe at node $i$ will do $b_{i,j} \,\mathrm{eV}$ of work against external forces.
The machine contains $m$ one-way pipes connecting the nodes. The $i$-th pipe connects $u_i$ and $v_i$, meaning a point charge can be transported from $u_i$ to $v_i$ (there is no limit on the number of times a pipe can be used). Assume that other forces inside the machine do no work, and you can control the trajectory of each point charge through the machine.
Every point charge fed into the machine must be extracted, and other forces inside the machine do no work. That is, if a point charge enters through the $i$-th pipe at node $x$ and exits through the $j$-th pipe at node $y$, the work done by the machine on it is $(h_x - h_y - a_{x,i} - b_{y,j}) \,\mathrm{eV}$.
Calculate the maximum total increase in kinetic energy (unit: $\mathrm{eV}$).
Input
The first line contains two positive integers $n, m$.
The next line contains $n$ integers, where the $i$-th number is $h_i$.
The next $m$ lines each contain two positive integers $u_i, v_i$ describing a one-way pipe.
The next $n$ lines each start with a positive integer $p_i$, followed by $p_i$ non-negative integers, where the $j$-th integer represents $a_{i,j}$.
The next $n$ lines each start with a positive integer $q_i$, followed by $q_i$ non-negative integers, where the $j$-th integer represents $b_{i,j}$.
Output
Output a non-negative integer representing the answer.
Examples
Input 1
3 4 3 9 2 1 1 2 3 3 3 3 2 1 2 1 0 1 2 1 1 1 2 1 1
Output 1
6
Examples 2~5
See the provided files.
Constraints
For $100\%$ of the data, it is guaranteed that $1 \le u_i, v_i \le n$ and $0 \le m, p_i, q_i, a_{i,j}, b_{i,j}, h_i$. Among these, $a_{i,j}, b_{i,j}, h_i$ are randomly generated with uniform probability within their respective ranges, and the rest are generated in a way that does not specifically target algorithms like SPFA.
| Test Case ID | $n \le$ | $m \le$ | $p_i, q_i \le$ | $a_{i,j}, b_{i,j} <$ | $h_i <$ | Special Property |
|---|---|---|---|---|---|---|
| $1, 2$ | $50$ | $200$ | $10$ | $10$ | $30$ | |
| $3, 4$ | $70$ | $300$ | $100$ | $100$ | $2000$ | |
| $5, 6, 7, 8$ | $100$ | $500$ | $200$ | $200$ | $10^4$ | |
| $9, 10$ | $2000$ | $5000$ | $500$ | $10^4$ | $10^6$ | A |
| $11, 12, 13, 14$ | $n-1$ | B | ||||
| $15, 16, 17, 18$ | $10^4$ | C | ||||
| $19, 20, 21$ | $700$ | $5000$ | $1000$ | $10^6$ | $10^8$ | |
| $22, 23, 24, 25$ | $2000$ | $2\times 10^4$ | $2000$ |
Special Property A: $|u_i - v_i| = 1$
Special Property B: $m = n - 1, u_i < v_i, v_i = i + 1$
Special Property C: $\min \{u_i, v_i\} \le 4$
Provided files
Due to the large scale of input and output for this problem, an I/O template is provided.
The compressed file contains five sample cases and an I/O template.