给定直线上的 $n$ 个线段 $[L_i, R_i]$。所有 $2n$ 个线段端点均为两两不同的整数。 该集合是层叠的（laminar）——即任意两个线段要么不相交，要么其中一个包含另一个。

请在每个线段中选择一个具有整数端点的非空子线段 $[l_i, r_i]$（满足 $L_i \le l_i < 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 < R_i \le 10^9$)，表示第 $i$ 个线段的端点。

所有给定的 $2n$ 个线段端点均不相同。线段集合是层叠的。

输出格式

第一行输出子线段长度之和的最大值。 接下来的 $n$ 行中，第 $i$ 行输出两个整数 $l_i$ 和 $r_i$ ($L_i \le l_i < r_i \le R_i$)，表示为第 $i$ 个线段选择的子线段。

样例

输入 1

4
1 10
2 3
5 9
6 7

输出 1

7
3 6
2 3
7 9
6 7

说明

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