P12907 [NERC 2020] Hard Optimization
题目背景
NERC 2020 原题要求给出一种方案，而 FJOI 2022 不要求。
题目描述
给定数轴上的 $n$ 个线段 $[L_i; R_i]$。所有 $2n$ 个线段端点为两两不同的整数。
这些线段构成一个 **层叠集**——任意两条线段要么不相交，要么其中一条完全包含另一条。
请为每个线段选择一个非空子线段 $[l_i, r_i]$（要求 $L_i \le l_i < r_i \le R_i$ 且端点为整数），使得这些子线段互不相交（允许端点重合），并且它们的长度之和（$\sum_{i=1}^n r_i - l_i$）达到最大。
输入格式
第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^3$）——线段数量。
接下来 $n$ 行，每行包含两个整数 $L_i$ 和 $R_i$（$0 \le L_i < R_i \le 10^9$）——第 $i$ 条线段的端点。
所有 $2n$ 个线段端点互不相同。给定的线段集合是层叠的。
输出格式
第一行输出子线段长度的最大可能和。
接下来的 $n$ 行，每行输出两个整数 $l_i$ 和 $r_i$（$L_i \le l_i < r_i \le R_i$），表示第 $i$ 条线段选择的子线段。
说明/提示
下图展示了示例输入和示例输出的对应关系。
翻译由 DeepSeek V3 完成