分数: 233 分
问题陈述
高桥正在玩 RPG 游戏。游戏有 N 任务,以及 i第任务 (1 \leq i \leq N) 的耐力消耗为 D_i 以及经验奖励 R_i。对于每个任务,他可以选择不清除它或只清除一次。
高桥的游戏风格是“只完成高效任务”。对于高桥来说, 高效的任务 是经验奖励至少为 K 倍其耐力消耗,即满足的任务 R_i \geq K \times D_i。在这里, K 是高桥设置的效率阈值乘数。
按照这种游戏风格,高桥清除了所有有效的任务,并且没有清除任何其他任务。
确定高桥按照这种游戏风格完成任务所获得的总经验值是否至少为目标经验值 T.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 100
- 1 \leq T \leq 10^{18}
- 1 \leq D_i \leq 10^4
- 1 \leq R_i \leq 10^9
- 所有输入均为整数
输入
N K T D_1 R_1 D_2 R_2 \vdots D_N R_N
- 第一行包含任务数量 N,效率阈值乘数 K,以及目标体验 T,用空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个任务的信息。
- 的 (1 + i)- 第行包含耐力消耗 D_i 以及经验奖励 R_i 的 i第一个任务,以空格分隔。
输出
如果高桥完成所有有效任务时获得的总经验值至少为目标经验值 T,打印 Yes;否则,打印 No.
示例输入 1
3 2 100 10 30 5 15 8 20
示例输出 1
No
示例输入 2
5 3 500 20 100 15 45 10 50 25 80 30 150
示例输出 2
No
示例输入 3
8 5 1000000000 100 600 200 1000 500 2500 1000 5000 300 1000 150 900 400 2000 250 1500
示例输出 3
No