← 返回题目列表

AtCoder · awc0055_e

E. 混合和目标量

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

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