P1069闲时自可期（rest）

【题目背景】

旧城钟楼的修缮已经接近尾声，负责整理档案的记录员只需守完最后一个工作日。工作通知会在固定时刻送达，他希望在不耽误任何安排的前提下，为自己留下尽可能多的闲暇。

【题目描述】

记录员的工作日共有 $n$ 分钟，依次编号为 $1\sim n$。当天共有 $k$ 项任务，第 $i$ 项任务会在第 $p_i$ 分钟开始，并持续 $t_i$ 分钟。若记录员选择处理这项任务，那么第 $p_i$ 分钟至第 $p_i+t_i-1$ 分钟都会被占用，他将在第 $p_i+t_i$ 分钟重新空闲。

每一分钟开始时，按照下列规则安排工作：

• 如果记录员正在处理一项任务，那么这一分钟开始的所有新任务都由其他人处理。
• 如果记录员此时空闲，并且有一项或多项任务开始，那么他必须从中选择恰好一项处理，其余任务由其他人处理。
• 如果记录员此时空闲，并且没有任务开始，那么这一分钟称为一分钟闲时。

已经交给其他人的任务不会再次交回，记录员也不能在一项任务结束前中途离开。请你合理选择需要处理的任务，求出这个工作日中最多能够获得多少分钟闲时。

【输入格式】

从文件 $\textbf{\textit{rest.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,k$，分别表示工作日的分钟数与任务数量。

接下来 $k$ 行，每行包含两个正整数 $p_i,t_i$，表示一项任务的开始时刻与持续时间。

【输出格式】

输出到文件 $\textbf{\textit{rest.out}}$ 中。

对于每组测试数据输出一行一个整数，表示记录员最多能够获得多少分钟闲时。

\newpage

【样例 1 输入】

10 2215 631 241 654 1168 578 1811 595 2102 2112 4

【样例 1 输出】

1423

【说明/提示】

【样例 1 解释】

在第一组测试数据中，可以在第 $1$ 分钟选择持续 $6$ 分钟的任务，在第 $8$ 分钟选择持续 $5$ 分钟的任务。这样第 $7,13,14,15$ 分钟均为闲时，共计 $4$ 分钟。

在第二组测试数据中，选择持续 $2$ 分钟的任务后，第 $1,4,5$ 分钟均为闲时，因此答案为 $3$。

【样例 2】

见选手目录下的 $\textbf{\textit{rest/rest2.in}}$ 和 $\textbf{\textit{rest/rest2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{rest/rest3.in}}$ 和 $\textbf{\textit{rest/rest3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{rest/rest4.in}}$ 和 $\textbf{\textit{rest/rest4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{rest/rest5.in}}$ 和 $\textbf{\textit{rest/rest5.ans}}$。

该组样例符合测试点 $13\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{rest/rest6.in}}$ 和 $\textbf{\textit{rest/rest6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq20$，$1\leq n,k\leq2\times10^5$，单个测试点内 $\sum n,\sum k\leq2\times10^5$，$1\leq p_i\leq n$，$1\leq t_i$，$p_i+t_i-1\leq n$。

特殊性质 A：有任务开始的时刻不超过 $20$ 个，并且每个时刻至多有两项任务开始。

特殊性质 B：对于每项任务，第 $p_i+t_i$ 分钟有其他任务开始，或 $p_i+t_i=n+1$。