题目描述

有一场有 $10^9$ 名编号从 $1$ 到 $10^9$ 的参赛者参加的大会。在这场大会中，将举办 $2$ 场竞赛。

作为竞赛的题目，准备了 $N$ 道编号从 $1$ 到 $N$ 的题目。对于第 $i$ 道题，如果被出题，则编号在 $L_i$ 到 $R_i$ 之间的所有参赛者都能答对，除此之外的参赛者都无法解答。

这些 $N$ 道题目需要分配到 $2$ 场竞赛中，每道题必须且只能在一场竞赛中被出题。同时，每场竞赛都必须至少有一道题目。

每场竞赛的“乐趣”定义为能解答该场所有题目的参赛者人数。请你求出两场竞赛乐趣之和的最大可能值。

输入格式

输入以以下格式从标准输入读入。

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

请输出两场竞赛乐趣之和的最大可能值。

样例 1

输入

4
4 7
1 4
5 8
2 5

输出

6

样例 2

输入

4
1 20
2 19
3 18
4 17

输出

34

样例 3

输入

10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526

输出

540049931

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $1 \leq L_i \leq R_i \leq 10^9$
• 输入的所有值均为整数。

样例解释 1

最优的分配方式如下：

• 在第 $1$ 场竞赛中出题 $1,3$。编号为 $5,6,7$ 的参赛者能解答该场所有题目，因此该场竞赛的乐趣为 $3$。
• 在第 $2$ 场竞赛中出题 $2,4$。编号为 $2,3,4$ 的参赛者能解答该场所有题目，因此该场竞赛的乐趣为 $3$。
• 两场竞赛的乐趣之和为 $6$。无法使乐趣之和超过 $6$。

由 ChatGPT 4.1 翻译