A83499.时间规划
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小明刚刚成为了管理官。由于太过兴奋,他接下了太多的工作。
现在的时间是 0。小明有 N 项工作,每项工作编号从 1 到 N。
完成第 i 项工作需要 Ai 单位时间。此外,第 i 项工作的截止时间为 Bi,也就是说,必须在时刻 Bi 之前完成这项工作。你可以恰好在时刻 Bi 完成工作。
小明一次只能做一项工作,但可以在完成一项工作后立即开始下一项工作。
请判断 小明是否能够在截止时间前完成所有工作。如果可以,输出 Yes;否则输出 No。
输入格式
输入以如下格式从标准输入读入:
N
A1 B1
A2 B2
⋯
AN BN
输出格式
如果能够在截止时间前完成所有工作,输出 Yes;否则输出 No。
输入输出样例
输入#1
5 2 4 1 9 1 8 4 9 3 12
输出#1
Yes
输入#2
3 334 1000 334 1000 334 1000
输出#2
No
输入#3
30 384 8895 1725 9791 170 1024 4 11105 2 6 578 1815 702 3352 143 5141 1420 6980 24 1602 849 999 76 7586 85 5570 444 4991 719 11090 470 10708 1137 4547 455 9003 110 9901 15 8578 368 3692 104 1286 3 4 366 12143 7 6649 610 2374 152 7324 4 7042 292 11386 334 5720
输出#3
Yes
说明/提示
限制条件
- 所有输入均为整数。
- 1≤N≤2×105
- 1≤Ai,Bi≤109 (1≤i≤N)
样例解释 1
例如,可以按如下顺序完成所有工作:
- 从时刻 0 到 1,做第 2 项工作。
- 从时刻 1 到 3,做第 1 项工作。
- 从时刻 3 到 7,做第 4 项工作。
- 从时刻 7 到 8,做第 3 项工作。
- 从时刻 8 到 11,做第 5 项工作。
注意,第 3 项工作恰好在截止时间 8 完成,这是允许的。