题目背景

Abiogenesis - Juggernaut.

本题为 Codeforces 1981 E. Turtle and Intersected Segments 改编。

题目描述

给 $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$ 的其中一个最小生成树形态如下：

【数据范围】

本题采用捆绑测试且开启子任务依赖。

• 特殊性质 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$。