A83499.时间规划

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小明刚刚成为了管理官。由于太过兴奋,他接下了太多的工作。

现在的时间是 00。小明有 NN 项工作,每项工作编号从 11NN

完成第 ii 项工作需要 AiA_i 单位时间。此外,第 ii 项工作的截止时间为 BiB_i,也就是说,必须在时刻 BiB_i 之前完成这项工作。你可以恰好在时刻 BiB_i 完成工作。

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

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

输入格式

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

NN
A1 B1A_1\ B_1
A2 B2A_2\ B_2
\cdots
AN BNA_N\ B_N

输出格式

如果能够在截止时间前完成所有工作,输出 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

说明/提示

限制条件

  • 所有输入均为整数。
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai,Bi109 (1iN)1 \leq A_i, B_i \leq 10^9\ (1 \leq i \leq N)

样例解释 1

例如,可以按如下顺序完成所有工作:

  • 从时刻 0011,做第 22 项工作。
  • 从时刻 1133,做第 11 项工作。
  • 从时刻 3377,做第 44 项工作。
  • 从时刻 7788,做第 33 项工作。
  • 从时刻 881111,做第 55 项工作。

注意,第 33 项工作恰好在截止时间 88 完成,这是允许的。

首页