AT_abc286_d [ABC286D] Money in Hand

题目描述

高桥君有 $N$ 种不同面额的硬币，每种硬币他各有若干枚。具体来说，对于 $1\leq i\leq N$，他有 $A_i$ 日元面额的硬币 $B_i$ 枚。

请判断高桥君能否用手头的硬币（且不能找零）恰好支付 $X$ 日元。

输入格式

输入以如下格式从标准输入读入。

$N$ $X$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

如果高桥君能用现有的硬币恰好支付 $X$ 日元，则输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

2 19
2 3
5 6

输出 #1

Yes

输入输出样例 #2

输入 #2

2 18
2 3
5 6

输出 #2

No

输入输出样例 #3

输入 #3

3 1001
1 1
2 1
100 10

输出 #3

Yes

说明/提示

限制条件

• $1\leq N\leq 50$
• $1\leq X\leq 10^4$
• $1\leq A_i\leq 100$
• $1\leq B_i\leq 50$
• 所有 $A_i$ 互不相同。
• 输入均为整数。

样例解释 1

高桥君有 $2$ 日元硬币 $3$ 枚，$5$ 日元硬币 $6$ 枚。可以用 $2$ 日元硬币 $2$ 枚和 $5$ 日元硬币 $3$ 枚，恰好支付 $2\times 2+5\times 3=19$ 日元。因此输出 Yes。

样例解释 2

无论如何组合手头的硬币，都无法恰好支付 $18$ 日元。因此输出 No。

样例解释 3

允许有某些硬币一枚也不使用。

由 ChatGPT 4.1 翻译