You are given a set of segments on a line . All segment endpoints are pairwise distinct integers.
The set is --- any two segments are either disjoint or one of them contains the other.
Choose a non-empty subsegment with integer endpoints in each segment () in such a way that no two subsegments intersect (they are allowed to have common endpoints though) and the sum of their lengths () is maximized.
输入格式
The first line contains a single integer () --- the number of segments.
The -th of the next lines contains two integers and () --- the endpoints of the -th segment.
All the given segment endpoints are distinct. The set of segments is laminar.
输出格式
On the first line, output the maximum possible sum of subsegment lengths.
On the -th of the next lines, output two integers and (), denoting the chosen subsegment of the -th segment.
样例
样例输入 1
4
1 10
2 3
5 9
6 7
样例输出 1
7
3 6
2 3
7 9
6 7
数据范围与提示
The example input and the example output are illustrated below.
