P1068梦的七重回旋（dream）

【题目背景】

你已经连续六夜回到同一场没有结局的梦。第七夜降临时，散落的梦境片段再次显现，你必须将它们编入两条彼此牵引的梦轨，让这次回旋在醒来前抵达尽可能完整的结局。

【题目描述】

这场梦中共有 $n$ 个等待编排的片段。第 $i$ 个片段会在时刻 $s_i$ 出现，持续 $t_i$ 个单位时间，并在时刻 $s_i+t_i$ 消散。

你可以将每个片段编入两条梦轨中的任意一条，也可以任由它从梦中消散。每个片段至多被编入一条梦轨。

同一条梦轨能够容纳同时出现的多个片段，因为它们仍然属于同一段梦境。两条梦轨却不能在一段非零长度的时间内同时出现片段，否则两段梦境便会争夺同一刻的意识，使第七次回旋立即破碎。

换言之，分别编入不同梦轨的任意两个片段，都不能在一段非零长度的时间内同时存在。一个片段恰好在另一个片段出现或消散的时刻结束或开始，不会使两条梦轨相互干扰。

对于一种合法的编排方案，设两条梦轨中分别编入了 $x$ 个与 $y$ 个片段，定义该方案的平衡度为 $\min(x,y)$。你希望让这场梦的平衡度尽可能大。

首先，请你求出没有额外限制时能够达到的最大平衡度。

梦境还要求你逐一确认每个片段能否成为这场回旋的一部分。对于每个 $1\leq i\leq n$，请你分别求出在第 $i$ 个片段必须被编入某一条梦轨时，能够达到的最大平衡度。第 $i$ 个片段可以被编入任意一条梦轨，其余片段仍然可以被编排或舍弃。

【输入格式】

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

本题包含多组测试数据。

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

对于每组测试数据：

第一行包含一个整数 $n$，表示片段数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $s_i,t_i$，分别表示第 $i$ 个片段出现的时刻与持续时间。

【输出格式】

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

对于每组测试数据，输出 $n+1$ 行。

第一行输出一个整数，表示没有额外限制时能够达到的最大平衡度。

接下来 $n$ 行，第 $i$ 行输出一个整数，表示第 $i$ 个片段必须被编入某一条梦轨时能够达到的最大平衡度。

【样例 1 输入】

10 12538 241 555 363 275 3

【样例 1 输出】

122231425262

【说明/提示】

【样例 1 解释】

没有额外限制时，可以将第 $1,4$ 个片段编入一条梦轨，将第 $3,5$ 个片段编入另一条梦轨，并舍弃第 $2$ 个片段。此时两条梦轨中均有 $2$ 个片段，平衡度为 $2$。

【样例 2】

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

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

【样例 3】

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

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

【样例 4】

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

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

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10$，$1\leq n\leq 200$，$0\leq s_i\leq 10^9$，$1\leq t_i\leq 10^9$。对于同一个测试点，保证 $\sum n\leq 200$。

【评分方式】

本题采用特殊判题方式。

若输出格式不正确，包括输出的整数数量不足或多于要求，则该测试点得 $0$ 分。

在输出格式正确的前提下，记以下两个条件分别为 A 与 B：

• A：所有测试数据中，没有额外限制时的答案均正确。
• B：所有测试数据中，每个片段必须被编入某一条梦轨时的答案均正确。

若 A、B 均满足，则该测试点取得全部分值。若只有 A 满足，则该测试点取得 $40\%$ 的分值。若只有 B 满足，则该测试点取得 $60\%$ 的分值。若 A、B 均不满足，则该测试点得 $0$ 分。