P16985 [NWERC 2018] 脱欧谈判 / Brexit Negotiations

译自 [NWERC 2018](https://2018.nwerc.eu/) B 题。

众所周知，脱欧谈判正在进行中——但我们仍然不知道它们是否真的能按时结束。 谈判会逐个主题进行。为了最有效地组织谈判，所有主题都会在单独的会议中讨论并最终确定，每次只开一个会议。 之所以采用这种制度，部分原因是某些主题之间存在非循环的依赖关系：例如，在决定关税同盟之前，就无法有意义地讨论关税问题。欧盟可以决定任意一种主题谈判顺序，只要满足这些依赖关系，并且所有主题都被讨论到。 每个主题都会使用所有可用资料进行充分讨论，其中也包括之前会议的重要结论。在每场会议开始时，代表们需要对已经发生过的每场会议各额外花费一分钟进行回顾，即使那些会议与当前主题无关，也要回顾它们的讨论过程并理解结论是如何得出的。下图给出了一个例子。 没有人喜欢冗长的会议。欧盟希望你帮助安排会议顺序，使得所有会议中最长的一场会议尽可能短。 :::align{center}  :::

输入包括： - 一行一个整数 $n$（$1\le n\le 4\cdot 10^5$），表示需要讨论的主题数量。主题编号为 $1$ 到 $n$。 - 接下来 $n$ 行，描述谈判主题。 第 $i$ 行首先包含两个整数 $e_i,d_i$（$1\le e_i\le 10^6$，$0\le d_i

输出在按照上述规则最优安排会议顺序时，所有会议中最长一场会议长度的最小可能值。

【数据规模与约定】 具体限制见输入格式。