狂暴的老师

题目背景

有 $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$ 的最小值。

样例 #1

样例输入 #1

3
5 1
1 4
2 2

样例输出 #1

2