# 狂暴的老师## 题目背景有 $n$ 个同学从 $0$ 开始编号在学习信奥课同学们排队向老师提问。每个同学问的问题不同因此答疑时长不同设第 $i$ 个同学的答疑时长为 $t_i$；每个同学的耐心值也不同设第 $i$ 个同学的耐心为 $p_i$。如果一个同学等待太久他会暴躁。每个同学的暴躁程度 $g_i$ 等于排在他前面的同学的答疑时长之和与自身耐心的差值即：$g_i=sum_j=0^i-1t_j

题目大意

有 $n$ 个同学（从 $0$ 开始编号）在学习信奥课，同学们排队向老师提问。每个同学问的问题不同，因此答疑时长不同，设第 $i$ 个同学的答疑时长为 $t_i$；每个同学的耐心值也不同，设第 $i$ 个同学的耐心为 $p_i$。 如果一个同学等待太久，他会暴躁。每个同学的暴躁程度 $g_i$ 等于排在他前面的同学的答疑时长之和与自身耐心的差值，即：$g_i=\sum_{j=0}^{i-1}t_j-p_i$。 如果同学们很暴躁，老师会狂暴。老师的狂暴程度 $r$ 等于所有同学暴躁程度 $g_i$ 的最大值，即：$r=\max_{i=0}^{n-1}g_i$。 改变 $n$ 个同学的排队顺序，老师的狂暴程度可能会发生变化。求所有的排队顺序中，老师的狂暴程度的最小值 $\min r$。

输入格式

从标准输入读入数据。 第一行为一个正整数 $n$（$1\le n\le1,000$），表示有 $n$ 位同学。 第二行到第 $n+1$ 行，每行两个整数，分别是 $t_i$（$0\le t_i\le 1,000$）和 $p_i$（$0\le p_i\le 1,000$）。

输出格式

输出到标准输出。 输出共一行，表示老师狂暴程度 $r$ 的最小值。

样例

输入样例：

3 5 1 1 4 2 2

输出样例：

思路

首先我们要对题目中的 $r$ 值进行分析，这个值等于所有学生的暴躁程度的最大值，因此，如果我们要求得最小的 $r$ 值，那就要在满足所有学生要求的前提下，尽可能缩小暴躁程度的最大值，这里我们可以采用二分答案的思想。

对于二分答案的思想，我们需要先进行一些准备工作，首先是对答案范围的确定。在做这道题时，我们可以发现 $r$ 的取值范围是在所有学生的答疑时长中的最大值 $t$ 和所有学生的耐心值中的最大值 $p$ 之间，因此我们可以对这个范围进行二分。

接下来，我们就要考虑如何进行二分了，这里我们可以采用贪心的思想。我们将所有同学按照答疑时长从小到大排列，然后对于每个同学，我们将其插入到所有已经排好序的同学当中，考虑这个同学的暴躁程度是否大于等于当前的答案，如果大于等于答案，那么就意味着这个同学会让老师狂暴，因此我们就要将这个同学插入到下一个位置，直到找到一个合适的位置。

在找到合适的位置之后，我们可以继续对下一个同学进行插入操作，直到所有的同学都排好序为止。最后，如果所有同学的暴躁程度都小于答案，那么就意味着当前的答案是可行的，因此我们可以将答案缩小到 $[l,mid]$，否则就将答案扩大到 $[mid+1,r]$。

代