AT_abc131_d [ABC131D] Megalomania

题目描述

现在的时间是 $0$。有 $N$ 项工作，每项工作编号从 $1$ 到 $N$。

完成第 $i$ 项工作需要 $A_i$ 单位时间。此外，第 $i$ 项工作的截止时间为 $B_i$，也就是说，必须在时刻 $B_i$ 之前完成这项工作。你可以恰好在时刻 $B_i$ 完成工作。

一次只能做一项工作，但可以在完成一项工作后立即开始下一项工作。

请判断是否能够在截止时间前完成所有工作。如果可以，输出 Yes；否则输出 No。

输入格式

输入以如下格式从标准输入读入：

$N$
$A_1\ B_1$
$A_2\ B_2$
$\cdots$
$A_N\ B_N$

输出格式

如果能够在截止时间前完成所有工作，输出 Yes；否则输出 No。

样例 1

输入

5
2 4
1 9
1 8
4 9
3 12

输出

Yes

样例 2

输入

3
334 1000
334 1000
334 1000

输出

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

输出

Yes

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9\ (1 \leq i \leq N)$

样例解释 1

例如，可以按如下顺序完成所有工作：

• 从时刻 $0$ 到 $1$，做第 $2$ 项工作。
• 从时刻 $1$ 到 $3$，做第 $1$ 项工作。
• 从时刻 $3$ 到 $7$，做第 $4$ 项工作。
• 从时刻 $7$ 到 $8$，做第 $3$ 项工作。
• 从时刻 $8$ 到 $11$，做第 $5$ 项工作。

注意，第 $3$ 项工作恰好在截止时间 $8$ 完成，这是允许的。

样例解释 2

无论以何种顺序完成工作，都无法在截止时间前完成所有工作。

由 ChatGPT 4.1 翻译