分数: 200 分
问题陈述
高桥负责工厂的质量控制。这家工厂生产 N 类型的产品,每个编号为 1 to N.
每个产品都有两个指标:“质量指数”和“产量”。产品质量指标 i is A_i,其日产量为 B_i 单位。质量指数越高,表明有缺陷的产品就越有可能出现。
高桥决定计算每种产品的“风险评分”。产品风险评分 i 定义为产品的质量指标 A_i 和生产数量 B_i,即 A_i \times B_i。风险评分越高意味着该产品需要更多关注。
高桥认为,风险评分为 K 或更高级别需要优先进行改进。查找风险评分为的产品数量 K 或更高。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 1 \leq A_i \leq 100 (1 \leq i \leq N)
- 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数。
输入
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
- 第一行包含一个整数 N 表示产品类型的数量和一个整数 K 代表风险评分阈值,以空格分隔。
- 从第 2 行到 (N+1)第行,给出了有关每个产品的信息。
- 的 树的 (i+1)第行 (1 \leq i \leq N) 包含质量指标 产品的 A_i 和生产数量 B_i 产品的 i,用空格分隔。
输出
输出风险评分为的产品数量 K 或更高版本,在一行中。
示例输入 1
3 100 10 5 20 10 5 30
示例输出 1
2
示例输入 2
5 500 15 40 8 100 50 20 30 15 25 25
示例输出 2
4