Megalomania

题目描述

Kizahashi 在 AtCoder 王国的 National Problem Workshop 被任命为 ABC 的管理员后，太兴奋而承担了过多的工作。 当前时间记为时间 $0$。Kizahashi 有 $N$ 项工作，编号为 $1$ 到 $N$。 Kizahashi 完成工作 $i$ 需要 $A_i$ 时间单位。工作 $i$ 的截止时间是时间 $B_i$，他必须在该时间之前或在该时间完成该工作。 Kizahashi 不能同时处理两个或更多工作，但当他完成一项工作后，可以立即开始另一项工作。 Kizahashi 能按时完成所有工作吗？如果能，输出 $Yes$；如果不能，输出 $No$。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $B_1$ $.$ $.$ $.$ $A_N$ $B_N$

输出格式

如果 Kizahashi 能按时完成所有工作，输出 $Yes$；如果不能，输出 $No$。

5
2 4
1 9
1 8
4 9
3 12

Yes

3
334 1000
334 1000
334 1000

No

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

Yes

提示

输入中的所有值均为整数。 $1 \leq N \leq 2 \times 10^5$ $1 \leq A_i, B_i \leq 10^9 (1 \leq i \leq N)$他可以按时完成所有工作，例如按以下顺序进行：

在时间 $0$ 到 $1$ 做工作 $2$。 在时间 $1$ 到 $3$ 做工作 $1$。 在时间 $3$ 到 $7$ 做工作 $4$。 在时间 $7$ 到 $8$ 做工作 $3$。 在时间 $8$ 到 $11$ 做工作 $5$。

注意在截止时间时间 $8$ 恰好完成工作 $3$ 是可以的。
无论他按什么顺序进行，都无法按时完成所有工作。

标签: AtCoder|abc131D

来源

AtCoder|abc131D