1032: 管理时间

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:166 通过:88

题目描述

        作为一名忙碌的商人,约翰知道必须高效地安排他的时间,他有N (1 <= N <= 1,000)份工作要做,比如给奶牛挤奶,清洗牛棚修理栅栏之类的。

        为了高效.列出了所有工作的清单,第i份工作需要T_i(1<=T_i<=1000)单位的时间来完成,而且必须在S_i(1<=S_i<=1000000)之前完成,同时注意约翰做一份工作必须直到做完才能停止。

 所有的商人都喜欢睡懒觉,请帮约翰计算他最迟什么时候开始工作,可以让所有工作按时完成。

输入格式

 1行输入N,之后N行每行输入一份工作的T_i和S_i

输出格式

最迟开始工作的时刻。如果没有答案,就输出-1 。

输入样例 复制

4
3 5
8 14
5 20
1 16

输出样例 复制

2

数据范围与提示

输入说明:约翰安排了4份工作,分别需要3, 8, 5 和 1个时间单位,当然这些工作需要在5, 14, 20 和 16 前完成。

输出说明:约翰最迟从第2个时间单位开始,按照1-> 2 -> 4-> 3的次序进行。