21992번 - Hard Optimization 스페셜 저지다국어

문제

You are given a set of $n$ segments on a line $[L_i; R_i]$. All 2ドルn$ segment endpoints are pairwise distinct integers.

The set is laminar --- any two segments are either disjoint or one of them contains the other.

Choose a non-empty subsegment $[l_i, r_i]$ with integer endpoints in each segment ($L_i \le l_i < r_i \le R_i$) in such a way that no two subsegments intersect (they are allowed to have common endpoints though) and the sum of their lengths ($\sum_{i=1}^n r_i - l_i$) is maximized.

입력

The first line contains a single integer $n$ (1ドル \le n \le 2 \cdot 10^3$) --- the number of segments.

The $i$-th of the next $n$ lines contains two integers $L_i$ and $R_i$ (0ドル \le L_i < R_i \le 10^9$) --- the endpoints of the $i$-th segment.

All the given 2ドルn$ segment endpoints are distinct. The set of segments is laminar.

출력

On the first line, output the maximum possible sum of subsegment lengths.

On the $i$-th of the next $n$ lines, output two integers $l_i$ and $r_i$ ($L_i \le l_i < r_i \le R_i$), denoting the chosen subsegment of the $i$-th segment.

제한

노트

The example input and the example output are illustrated below.