← 返回题目列表

Codeforces · 1510/H

H. 硬优化

中文机器翻译题面 查看原题

在 $$$[L_i 行上给你一组 $$$n$$$ 线段; R_i]$$$。所有 $$$2n$$$ 段端点都是成对不同的整数。

该套装是 层流 — 任意两个线段要么不相交,要么其中一个包含另一个。

选择一个非空子段 $$$[l_i, r_i]$$$,每个段中都有整数端点 ($$$L_i \le l_i \lt r_i \le R_i$$$),使得两个子段不相交(但允许它们有公共端点)及其长度总和 ($$$\sum_{i=1}^n r_i - l_i$$$) 最大化。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^3$$$) — 段数。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$L_i$$$ 和 $$$R_i$$$ ($$$0 \le L_i \lt R_i \le 10^9$$$) — 第 $$$i$$$ 段的端点。

所有给定的 $$$2n$$$ 段端点都是不同的。该组段是层状的。

输出

在第一行,输出子段长度的最大可能总和。

在接下来的 $$$n$$$ 行的第 $$$i$$$ 行上,输出两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$L_i \le l_i \lt r_i \le R_i$$$),表示第 $$$i$$$ 段的所选子段。

示例

输入
复制

4
1 10
2 3
5 9
6 7

输出
复制

7
3 6
2 3
7 9
6 7

注意

示例输入和示例输出如下所示。