【MX-X5-T6】「GFOI Round 1」Abiogenesis

> [Abiogenesis - Juggernaut.](https://music.163.com/#/song?id=1416321652) 本题为 [Codeforces 1981 E. Turtle and Intersected Segments](https://codeforces.com/contest/1981/problem/E) 改编。

给 $n$ 条线段 $[l_i, r_i]$，第 $i$ 条线段有一组权值 $a_i, b_i$。 有一个无向图 $G$，其初始有 $n$ 个结点，$0$ 条边。对于每一对正整数 $i, j$ 满足 $1 \le i < j \le n$，若编号为 $i, j$ 的线段相交，就在 $G$ 中连一条两个端点分别为 $i, j$，边权为 $a_i + a_j + |b_i - b_j|$ 的边。 求 $G$ 最小生成树边权之和，或报告 $G$ 不连通。 如果两条线段 $[l_1, r_1]$ 和 $[l_2, r_2]$ 满足 $\max(l_1, l_2) \le \min(r_1, r_2)$，就认为它们是相交的。

**本题有多组测试数据。** 第一行输入一个正整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行包含一个正整数 $n$，表示线段的个数。 之后的 $n$ 行中的第 $i$ 行包含四个正整数 $l_i, r_i, a_i, b_i$。

对于每组数据，输出一行一个整数，表示 $G$ 最小生成树边权之和。特别地，若 $G$ 不连通，输出 $-1$。

4
5
1 7 1 3
2 4 2 6
3 5 3 5
6 7 2 9
3 4 1 4
5
2 7 3 3
1 3 5 6
4 5 3 5
6 7 1 9
1 1 5 4
4
1 4 1 3
1 2 2 1
3 4 3 5
1 4 4 4
3
1 3 1 1
2 3 1 3
4 5 1 8

22
41
17
-1

**【样例解释】** 对于第一组数据，$G$ 的形态如下：  $G$ 的其中一个最小生成树形态如下：  **【数据范围】** **本题采用捆绑测试且开启子任务依赖。** | 子任务编号 | $n \le$ | $\sum n \le$ | 特殊性质 | 子任务依赖 | 分值 | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $100$ | $10^5$ | 无 | 无 | $11$ | | $2$ | $10^5$ | $10^5$ | AC | 无 | $5$ | | $3$ | $10^5$ | $10^5$ | A | $2$ | $14$ | | $4$ | $10^5$ | $10^5$ | B | 无 | $14$ | | $5$ | $10^5$ | $10^5$ | C | $2$ | $14$ | | $6$ | $10^5$ | $10^5$ | D | 无 | $14$ | | $7$ | $10^5$ | $10^5$ | 无 | $1, 2, 3, 4, 5, 6$ | $28$ | - 特殊性质 A：$\forall i \in [1, n], l_i = 1$。 - 特殊性质 B：$\forall i \in [1, n - 1], l_i \le l_{i + 1}, r_i \le r_{i + 1}$。 - 特殊性质 C：$\forall i \in [1, n], b_i = 1$。 - 特殊性质 D：$\forall i \in [1, n], a_i = b_i$。 对于所有数据，满足 $1 \le T \le 10^4$，$1 \le n, \sum n \le 10^5$，$1 \le l_i, r_i, a_i, b_i \le 10^8$，$l_i \le r_i$。