分数: 600 点
问题陈述
10^9 参赛者,编号 1 to 10^9,将参加一场比赛。 本次比赛将设两场比赛。
主办方准备 N 问题,已编号 1 to N,在这些比赛中使用。 当出现问题时 i 在竞赛中出现,将由参赛者中的所有参赛者解决 L_i 致参赛者 R_i (含),并且不会被任何其他参赛者解决。
主办方将使用这些 N 两次竞赛中的问题。 每个问题必须在一场比赛中使用,并且每场比赛必须至少有一个问题。
的 喜悦 每场比赛的 是解决比赛中所有问题的参赛者人数。 找出两场比赛的最大可能的总快乐。
约束
- 2 \leq N \leq 10^5
- 1 \leq L_i \leq R_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
输出
打印两场比赛的最大可能的总快乐。
示例输入 1
4 4 7 1 4 5 8 2 5
示例输出 1
6
最佳选择是:
- 使用问题 1 和 3 在第一场比赛中。参赛者 5, 6,和 7 都会解决这两个问题,所以这次比赛的乐趣在于 3.
- 使用问题 2 和 4 在第二场比赛中。参赛者 2, 3,和 4 都会解决这两个问题,所以这次比赛的乐趣在于 3.
- 这两场比赛总的欢乐程度是 6。我们不能让总的快乐大于 6.
示例输入 2
4 1 20 2 19 3 18 4 17
示例输出 2
34
示例输入 3
10 457835016 996058008 456475528 529149798 455108441 512701454 455817105 523506955 457368248 814532746 455073228 459494089 456651538 774276744 457667152 974637457 457293701 800549465 456580262 636471526
示例输出 3
540049931