#P18862. [Croatian CPC2025] Jalovo Junaštvo

[Croatian CPC2025] Jalovo Junaštvo

Jalovo Junaštvo

题目描述

一条道路上有 NN 个团伙。第 ii 个团伙控制区间 [ai,bi][a_i,b_i]。任意两个不同的团伙 i,ji,j 均不满足 ai≤aja_i\le a_j 且 bj≤bib_j\le b_i,即不存在一个区间被另一个区间包含的情况。

现在需要为每个团伙重新分配一个区间,满足:

  • 新区间包含在该团伙原来的区间中。
  • 所有新区间的长度相同。
  • 新区间的内部两两不相交,但允许在端点处相接。

求新区间长度的最大值。新区间的端点不要求是整数。

输入格式

第一行包含整数 NN。

接下来 NN 行,每行包含两个整数 ai,bia_i,b_i。

输出格式

以最简分数 p/q 的形式输出最大长度。

数据范围

  • 1≤N≤1000001\le N\le100000。
  • 0≤ai<bi≤10000000\le a_i<b_i\le1000000。
  • 不存在两个不同的区间满足 ai≤aja_i\le a_j 且 bj≤bib_j\le b_i。

样例 1

输入

3
2 6
1 4
8 12

输出

5/2

样例 2

输入

2
0 3
1 4

输出

2/1