情报污染

Problem Description

小 Q 是比特国的一名特工，正在执行一项秘密任务，负责污染敌方的情报，提高敌方破译的难度。 以下是敌方收集到的所有情报：

• 在海里分布着 $n$ 艘潜艇，编号依次为 $1,2,\dots,n$。第 $i$ 艘潜艇的经纬度坐标为（$x_i,y_i$），射程 $r_i$ 敌方未知，只知道是个正实数。
• $a$ 条 A 类情报，每条情报包含 $u,v$，表示潜艇 $u$ 和潜艇 $v$ 可以共同打击某一目标，即：[r_u+r_v\geq dis(u,v)=\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}]
• $b$ 条 B 类情报，每条情报包含 $u,v,w$，表示潜艇 $u$ 和潜艇 $v$ 中射程较长的至少是 $w$ 射程，即：[\max(r_u,r_v)\geq w]
• $c$ 条 C 类情报，每条情报包含 $u,v,w$，表示潜艇 $u$ 和潜艇 $v$ 中射程较短的至多是 $w$ 射程，即：[\min(r_u,r_v)\leq w] 如果敌方发现不存在一组正实数 $r_1,r_2,\dots,r_n$ 满足所有情报，就需要耗费大量的时间去重新考证每条情报的可靠性，对比特国有利。小 Q 需要判断当前情报是否已经可以让敌方启动情报考证工作，若不能，他可以黑入敌方的情报网，选择性地植入 $d$ 条 D 类情报中的一部分或全部。第 $i$ 条 D 类情报为潜艇 $u_i$ 的射程不超过 $w_i$，但是植入代价为 $p_i$。 请写一个程序，帮助小 Q 以最小的总代价植入情报，使得不存在一组正实数 $r_1,r_2,\dots,r_n$ 满足所有情报。

Input

第一行包含一个正整数 $T$（$1\leq T\leq 500$），表示测试数据的组数。 每组数据第一行包含五个整数 $n,a,b,c,d$（$2\leq n\leq 50\,000$, $0\leq a,b,c\leq 50\,000$, $0\leq d\leq 250$），分别表示潜艇的数量以及每类情报的数量。 接下来 $n$ 行，每行两个正整数 $x_i,y_i$（$1\leq x_i,y_i\leq n$），分别表示每艘潜艇的坐标。不同潜艇可以位于同一个坐标。 接下来 $a$ 行，每行两个正整数 $u,v$（$1\leq u < v\leq n$），依次描述每条 A 类情报。A 类情报不会重复。 接下来 $b$ 行，每行三个正整数 $u,v,w$（$1\leq u < v\leq n$, $1\leq w\leq n$），依次描述每条 B 类情报。B 类情报的（$u,v$）不会重复。 接下来 $c$ 行，每行三个正整数 $u,v,w$（$1\leq u < v\leq n$, $1\leq w\leq n$），依次描述每条 C 类情报。C 类情报的（$u,v$）不会重复。 接下来 $d$ 行，每行三个正整数 $u_i,w_i,p_i$（$1\leq u_i,w_i\leq n$, $1\leq p_i\leq 10^9$），依次描述每条 D 类情报。D 类情报的 $u_i$ 不会重复。 输入数据保证 $\sum n\leq 400\,000$, $\sum a\leq 400\,000$, $\sum b\leq 400\,000$ 且 $\sum c\leq 400\,000$。

Output

对于每组数据输出一行一个整数，即最小的总代价。如果无需植入，请输出 “$\texttt{0}$”；若无解请输出 “$\texttt{-1}$”。

Sample 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

Sample Output

-1
0
5

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）