解题思路

• 裁剪到工作范围：只保留与 $[1, H]$ 相交的区间，并将其裁剪到该范围内。
• 排序并合并：按左端点排序，依次合并所有重叠或相邻的区间（即 $l \le r_{\text{cur}} + 1$ 时合并）。
• 求覆盖长度：合并后各段长度相加（闭区间长度为 $r-l+1$），得到 $U$。
• 最终答案：$\text{ans} = H - U$，若无区间则 $\text{ans} = H$。
• 复杂度：排序主导，时间 $O(N \log N)$，空间 $O(1)$ 额外（不计输入存储）。

题目内容

城市公路某些路段路面质量下降，多多需要对这些路段进行维修。多多可进行工作的时间为 $1$～$H$ 。

同时有交通管理系统会根据不同因素发出拥堵预警：天气预报显示可能有暴雨、大型活动预计车流剧增、早晚高峰时期等。

多多的维修应当在路况不繁忙的时候进行，需要注意预警时段可能存在重叠，比如雨天预警 $[10,25]$ 和活动预警 $[15,25]$ 同时存在，则需要避开整个 $[10,25]$ 时段进行维修

请你帮助多多计算可以进行公路维修的时间共有多少

输入描述

第一行为一个整数 $T$ ,表示共有 $T$ 个测试数据 $(1<= T<= 10)$

每组测试数据：

第一行为一个整数 $H$ ，表示多多可进行维修的工作总时长 $(1 <= H <= 10^9)$

第二行为一个整数 $N$ ，表示预警时段的个数 $(1<=N<= 100000)$

接下来的 $N$ 行：

每行输入两个整数 $xi,yi$ , 表示区域 $[xi,yi]$ 被预警将有拥堵发生 $(1 <= xi <= yi<= H)$

输出描述

每组数据输出一个结果，每个结果占一行

补充说明

对于 $20$% 的数据有：$1<=H<= 10^6,1 <= N <= 1000$

对于 $100$% 的数据有：$1<=H<= 10^9,1 <=N <= 100000$

样例1

输入

1
10
2
5 10
5 5

输出

4

说明

多多仅能在 $1$ ~ $4$ 的时间段内进行维修，工作时长为 $4$

样例2

输入

1
3
1
1 3

输出

0

说明

多多的工作时间内全是拥堵预警，无法进行维修

样例3

输入

1
5
2
1 2
4 5

输出

1

说明

多多仅能在$3$~$3$的时间段内进行维修，工作时长为$1$