分数: 466 分
问题陈述
高桥是一名冒险家。探索地牢后他发现 N 宝箱。
的 i第-个宝箱的重量为 A_i 公斤和价值 B_i.
高桥的背包最多可以容纳总重量为 M 公斤。高桥计划从宝箱中选择一定数量的宝箱(可能是零) N 箱子可以放入背包并带回家。然而,由于每个宝箱仅存在一次,因此无法多次选择同一个宝箱。
高桥想要最大化所选宝箱的总价值,但受限于所选宝箱的总重量最多为 M 公斤。使总价值最大化的选择称为 最优选择。可能存在多个最优选择。
对于每个宝箱 i (1 \leq i \leq N),判断是否存在包含宝箱的最优选择 i.
约束
- 1 \leq N \leq 1,000
- 1 \leq M \leq 3,000
- 1 \leq A_i \leq M (1 \leq i \leq N)
- 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N M A_1 B_1 A_2 B_2 \vdots A_N B_N
- 第一行包含一个整数 N 代表宝箱数量和一个整数 M 代表背包的容量,以空格分隔。
- 的 (i + 1)第行 (1 \leq i \leq N) 包含一个整数 A_i 代表重量 i- 第一个宝箱和一个整数 B_i 代表其值,以空格分隔。
输出
打印 N 行。
关于 i第行,打印 Yes 如果存在包含宝箱的最佳选择 i,和 No 否则。
示例输入 1
3 5 2 3 3 4 3 3
示例输出 1
Yes Yes No
示例输入 2
4 4 2 5 2 5 2 5 3 1
示例输出 2
Yes Yes Yes No
示例输入 3
6 8 3 5 4 6 5 7 2 3 1 1 6 8
示例输出 3
Yes Yes Yes No Yes No
示例输入 4
10 15 3 10 4 12 5 14 2 7 1 3 6 18 7 20 8 22 3 9 4 11
示例输出 4
Yes Yes No Yes Yes Yes No No Yes No
示例输入 5
1 1 1 1
示例输出 5
Yes