← 返回题目列表

AtCoder · awc0006_b

B. 高效的任务

中文机器翻译题面 查看原题

分数: 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