← 返回题目列表

AtCoder · agc040_b

B. 两项比赛

中文机器翻译题面 查看原题

分数: 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