分数: 433 分
问题陈述
高桥有 N 化学品类型。的 i-th化学品有两种使用模式:正常模式和加热模式。在正常模式下使用它会产生 A_i mL 溶液,并在加热模式下使用它产生 B_i 毫升溶液。
高桥从这些化学品中选择了其中一些(可能是零),并且对于每种选定的化学品,独立决定是否在正常模式或加热模式下使用它。每种化学品最多可以使用一次。确定从所选化学品中获得的溶液总量是否可能准确 K 毫升。
如果可能,输出 Yes;如果不可能,则输出 No.
约束
- 1 \leq N \leq 26
- 0 \leq K \leq 10^{15}
- 1 \leq A_i \leq 10^{14}
- 1 \leq B_i \leq 10^{14}
- 所有输入值均为整数。
输入
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
- 第一行包含一个整数 N 代表化学品的种类数量,整数 K 代表溶液的目标量,以空格分隔。
- 以下 N 行提供有关每种化学品的信息。
- 的 树的 (1 + i)第行包含正常模式下产生的数量 A_i 和加热模式下的产量 B_i 为 i-th 化学品,以空格分隔。
输出
如果从所选化学品中获得的溶液总量可能恰好是 K 毫升,输出 Yes;否则,输出 No 在一行上。
示例输入 1
3 10 3 5 4 6 1 8
示例输出 1
Yes
示例输入 2
2 5 2 4 6 8
示例输出 2
No
示例输入 3
8 57 11 14 7 10 9 15 13 20 17 18 6 16 8 12 5 21
示例输出 3
Yes
示例输入 4
20 590000000000000 10000000000000 11000000000000 12000000000000 13000000000000 14000000000000 15000000000000 16000000000000 17000000000000 18000000000000 19000000000000 20000000000000 21000000000000 22000000000000 23000000000000 24000000000000 25000000000000 26000000000000 27000000000000 28000000000000 29000000000000 30000000000000 31000000000000 32000000000000 33000000000000 34000000000000 35000000000000 36000000000000 37000000000000 38000000000000 39000000000000 40000000000000 41000000000000 42000000000000 43000000000000 44000000000000 45000000000000 46000000000000 47000000000000 48000000000000 49000000000000
示例输出 4
Yes
示例输入 5
1 0 1 100000000000000
示例输出 5
Yes