题目描述

给定 $n,m,k$ 和 $k$ 条信息 $(X,L,R,C)$，考虑一个 $n$ 个点的有向图，初始对于 $\forall 1 \leq i \neq j \leq n$，$i$ 和 $j$ 之间有一条权值为 $0$ 的边。

对于每一条信息 $(X,L,R,C)$，$\forall i \in [L,R]$ 在图中从 $i$ 向 $X$ 连一条边权为 $C$ 的边。

求其最大权外向森林，满足森林中有 $m$ 个弱连通块，输出其权值和。

输入格式

有多组输入数据，第一行一个整数 $T(1 \leq T \leq 2)$ 表示数据组数。

对于每组数据第一行三个整数 $n,m,k(1 \leq m \leq n \leq 10^5 , 1 \leq k \leq 2 \times 10^5)$，接下来 $k$ 行每行四个整数 $X,L,R,C(1 \leq X_i \leq n , 1 \leq L_i \leq R_i \leq n , 0 \leq C_i \leq 10^9)$ 描述一条信息。

输出格式

对于每组数据一行一个整数表示最大权 $m$ 连通块内向森林权值和。

样例输入 1

1
3 1 3
1 1 3 600000
1 3 3 666666
3 1 1 173768

样例输出 1

773768

时间限制：$4$ s

空间限制：$512$ MB