G1-布置考场（exam）

题目背景

Lsxszc要穷途末路了！于是他决定去找oOoOoOOOooOO出题。

oOoOoOOOooOO现在正在布置考场！于是Lsxszc打算帮oOoOoOOOooOO布置考场，这样oOoOoOOOooOO就可以早一点出题了。

题目描述

一共有 $T$ 个校区（多测）。

在长度为 $n$ 的校园里，有 $m$ 个考场需要布置，第 $i$ 个考场域覆盖区间 $[l_i, r_i]$。

现在Lsxszc和oOoOoOOOooOO要开始工作，他们各自可以选择一段长度恰好为 $k$ 的工作区域（左端点可以是任意整数，不要求落在 $[1,n]$ 范围内），分别记为：

• Lsxszc负责区间 $L_{\text{L}}$，长度为 $k$
• oOoOoOOOooOO负责区间 $L_{\text{0}}$，长度为 $k$

每个考场 $[l_i, r_i]$ 必须指派给Lsxszc或oOoOoOOOooOO负责：

• 若指派给Lsxszc，则贡献为它与 $L_{\text{L}}$ 的相交长度；
• 若指派给oOoOoOOOooOO，则贡献为它与 $L_{\text{0}}$ 的相交长度；
• 若不相交，则贡献为 $0$。

Lsxszc迫不及待想让oOoOoOOOooOO出题，于是Lsxszc打算计算一下怎么分配最优，但是oOoOoOOOooOO在 $1$ 秒内就算出了结果，现在他决定考考Lsxszc，Lsxszc当然不会，于是向你求助。请你告诉他，如何选择Lsxszc和oOoOoOOOooOO的负责区间的位置，并为每个考场分配负责者，使所有考场的贡献总和最大。

输入格式

$T$

$n_1 \ \ m_1 \ \ k_1$

$l_{1,1} \ \ r_{1,1}$

$l_{1,m_1} \ \ r_{1,m_1}$

$\dots$

$n_T \ \ m_T \ \ k_T$

$l_{T,1} \ \ r_{T,1}$

$l_{T,m_T} \ \ r_{T,m_T}$

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

14
8
2
8

说明/提示

数据范围

对于所有测试点：

• $t(1 \leq t\leq 10)$
• $1\leq n,m\leq 100000, 1\leq k\leq n$。
• $\sum \max(n, m) \lt 100000$
• 保证$1 \le l_i \le r_i \le n$

后记

Lsxszc：我不会我不会我不会！！！！

oOoOoOOOooOO：$\dots$ (此处省略 $10^9$ 字讲解)

谢谢你！oOoOoOOOooOO！