配点 : 600 点
問題文
企鹅君现已上线 N 工作必须完成。i\ (1 \leq i \leq N) 第二份工作是明天。 1 当日 L_i 从第一天开始 R_i 直到那一天 就在 R_i-L_i+1 天 1 您需要选择一天并利用这一整天来完成此操作。正如它所说,如果你使用它一整天,他就会 1 您无法在一天内执行多项任务。
企鹅君 i 第一份工作 D_i 在他的那天完成时 悲伤 定义如下。
- S=(D_1,D_2,\ldots,D_N) 按升序排序的序列为 S' ,\max_{1 \leq i \lt N} (S'_{i+1}-S'_i)
请尽量减少企鹅的悲伤。不过,首先,企鹅君
如果您无法完成所有 N 任务,-1 。
制約
- 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
\hspace{0.6cm}\vdots
L_N R_N
出力
企鹅君 N 如果他能够完成所有任务,那么他的悲伤值最低为 -1 。
入力例 1
3 1 3 2 3 3 5
出力例 1
1
例如,
- 1 第一份工作 3 当天
- 2 第一份工作 2 当天
- 3 第一份工作 4 当天
这样做,企鹅君感到悲伤。 1 。企鹅君 1 这是最小值,因为您一天不能完成一项以上的工作。
入力例 2
3 1 1 2 2 1 2
出力例 2
-1
企鹅君 N 我无法完成所有任务。
入力例 3
8 157966192 957651261 451709097 715397956 273397483 342666952 165622095 585411299 749846702 972016434 8431836 421375441 459940001 999343267 7784836 829109033
出力例 3
58168536
原案: 企鹅人