P12907 [NERC 2020] Hard Optimization

You are given a set of $n$ segments on a line $[L_i; R_i]$. All $2n$ segment endpoints are pairwise distinct integers. The set is $\emph{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 $2n$ 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.