J. Jamming of Intelligence
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Narwhy, an underdog underwater undercover agent of Byteland, is executing a signal jamming operation against enemy intelligence networks. His objective is to introduce inconsistencies into the enemy's surveillance data to disrupt their decryption efforts.

The enemy's current intelligence database contains:

  • $$$n$$$ submarines, numbered $$$1,2,\dots,n$$$, each positioned at coordinates $$$(x_i,y_i)$$$. Their firing ranges $$$r_i$$$ are unknown positive real values.
  • $$$a$$$ signal overlap reports: each specifying submarines $$$u$$$ and $$$v$$$ that can jointly engage a target, forming a coverage constraint: $$$$$$ r_u + r_v \ge \operatorname{dist}(u,v)=\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}. $$$$$$
  • $$$b$$$ maximum range signatures: each indicating that between submarines $$$u$$$ and $$$v$$$, the stronger emitter has range at least $$$w$$$: $$$$$$ \max(r_u,r_v) \ge w. $$$$$$
  • $$$c$$$ minimum range signatures: each indicating that between submarines $$$u$$$ and $$$v$$$, the weaker emitter has range at most $$$w$$$: $$$$$$ \min(r_u,r_v) \le w. $$$$$$

Narwhy's jamming strategy is to make the entire dataset inconsistent—ensuring no assignment of positive values $$$r_1,\dots,r_n$$$ can satisfy all constraints. This would force the enemy into time-consuming signal verification.

If the existing intelligence is already inconsistent, no action is needed. Otherwise, Narwhy can inject some of the given $$$d$$$ range suppression signals into the network. The $$$i$$$-th such signal imposes an upper bound $$$w_i$$$ on submarine $$$u_i$$$'s range, but each injection carries an operational cost $$$p_i$$$.

Since Narwhy's main expertise is actually in narwhal tusk operations, he needs your help! Determine the minimum total cost to jam the intelligence system by selecting suppression signals to create an unsatisfiable constraint set.

Input

The first line contains an integer $$$T~(1 \le T \le 500)$$$, representing the number of test cases.

For each test case:

  • The first line contains five integers $$$n, a, b, c, d ~(2 \le n \le 5\times 10^4, 0 \le a, b, c \le 5\times 10^4,0 \le d \le 250)$$$, representing the number of submarines, signal overlap reports, maximum range signatures, minimum range signatures, and available suppression signals respectively.
  • For the next $$$n$$$ lines, each line contains two integers $$$x_i, y_i~(1\le x_i,y_i\le n)$$$, representing the coordinates of submarine $$$i$$$.
  • For the next $$$a$$$ lines, each line contains two integers $$$u, v~(1 \le u \lt v \le n)$$$, representing a signal overlap report. It is guaranteed that no unordered pair $$$(u, v)$$$ appears more than once among all the signal overlap reports.
  • For the next $$$b$$$ lines, each line contains three integers $$$u, v, w~(1 \le u \lt v \le n, 1\le w\le n)$$$, representing a maximum range signature. It is guaranteed that no unordered pair $$$(u, v)$$$ appears more than once among all the maximum range signatures.
  • For the next $$$c$$$ lines, each line contains three integers $$$u, v, w~(1 \le u \lt v \le n, 1\le w\le n)$$$, representing a minimum range signature. It is guaranteed that no unordered pair $$$(u, v)$$$ appears more than once among all the minimum range signatures.
  • For the next $$$d$$$ lines, each line contains three integers $$$u_i, w_i, p_i~(1\le u_i,w_i\le n, 1\le p_i\le 10^9)$$$, representing an available suppression signal. It is guaranteed that no submarine $$$u$$$ appears more than once among all the available suppression signals.

It is guaranteed that for all test cases, $$$\sum n\le 4\times 10^5,\sum a\le 4\times 10^5,\sum b\le 4\times 10^5,\sum c\le 4\times 10^5$$$.

Output

For each test case, output a single integer:

  • "0" if no insertion is needed;
  • otherwise "-1" if it is impossible;
  • otherwise the minimum total cost required.
Example
Input
3
2 0 0 0 1
1 1
1 1
2 2 100
4 3 0 3 0
1 1
4 4
1 4
2 3
1 2
1 3
2 3
1 2 1
1 3 1
2 3 1
3 1 1 1 2
1 1
1 2
3 3
1 3
2 3 2
1 2 1
3 1 5
2 1 7
Output
-1
0
5