在 $$$[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
注意
示例输入和示例输出如下所示。
