#P2920. 时间管理
时间管理
题目描述
作为一名忙碌的商人,约翰知道必须高效地安排他的时间。他有 N(1≤N≤1000) 个工作要做,比如给奶牛挤奶,清洗牛棚,修理栅栏之类的。
为了高效,约翰列出了所有工作的清单。第 i(1≤i≤N) 个工作需要 Ti (1≤Ti≤1000) 单位的时间来完成,而且必须在 1≤Si≤1000000 或之前完成。现在是 0 时刻。约翰做一份工作必须直到做完才能停止。
所有的商人都喜欢睡懒觉。请帮约翰计算他最迟什么时候开始工作,可以让所有工作按时完成。(如果始终无法完成全部任务,输出 −1)
输入格式
-
Line 1: A single integer: N
-
Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and S_i
输出格式
- Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.
输入输出样例
4
3 5
8 14
5 20
1 16
2
说明/提示
Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of time, respectively, and must be completed by time 5, 14, 20, and 16, respectively.
Farmer John must start the first job at time 2. Then he can do the second, fourth, and third jobs in that order to finish on time.