← 返回题目列表

AtCoder · codefestival_2015_final_d

D. 足部游戏二

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

問題文

高桥君打算挑战如下的节奏游戏。

  • 有一个大按钮 N 个。要按这个按钮 1 个人正好需要 1 个人,没有其他方法可以按。
  • 1 的人同一时间不能 2 个以上的按钮。
  • i 个按钮,从 S_i 到 T_i 一直按到……为止 1 可以获得。这时,不必一定由同一个人从头到尾一直按着,也可以在途中更换按的人。
  • 上下按钮所花费的时间,或更换按按钮的人所花费的时间,可以忽略不计。

高桥君希望通过几个人协力玩这个游戏, N-1 获得超过 分的成绩。N-1 请找出获取至少这些分数所需的最小最小值。


入力

输入是按以下格式从标准输入给出的。

N
S_1 T_1
S_2 T_2
:
S_N T_N
  • 1 行表示按钮数量的整数 N (2 ≦ N ≦ 10^5) 。 来自行
  • 2 从线 N 行给出了每个按钮的信息。其中 i (1 ≦ i ≦ N) 行中,2 整数 S_i, T_i (1 ≦ S_i < T_i ≦ 10^5) 。这是i 个按钮,从 S_i 到 T_i 一直按到……为止 1 表示可以获得分数。

出力

N-1 为了获得至少这些分数所需的最小最小值 1 行输出。在输出末尾插入换行符。


入力例1

4
1 4
1 2
2 3
3 4

出力例1

1

下图显示了每个按钮在持续按下时可以获得分数的时间。按钮 1 以外的按钮 1 全部踩到人就可以 3 得到点数。

figure1

入力例2

5
5 11
2 4
3 4
2 7
5 7

出力例2

2

入力例3

4
1 2
1 2015
2015 100000
99999 100000

出力例3

2