← 返回题目列表

AtCoder · tkppc6_1_o

O. 企鹅君的工作计划

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

配点 : 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

原案: 企鹅人