問題文

ペンギンくんはこれから 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
• 入力は全て整数

入力例 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

原案: penguinman