atcoder#ABC286D. [ABC286D] Money in Hand

[ABC286D] Money in Hand

配点 : 400400

問題文

高橋君は NN 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1iN1\leq i\leq N について AiA_i 円硬貨を BiB_i 枚持っています。

高橋君が現在持っている硬貨を用いて、(お釣りが出ないように)ちょうど XX 円を支払うことができるか判定してください。

制約

  • 1N501\leq N\leq 50
  • 1X1041\leq X\leq 10^4
  • 1Ai1001\leq A_i\leq 100
  • 1Bi501\leq B_i\leq 50
  • AiA_i はすべて異なる。
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

NN XX

A1A_1 B1B_1

A2A_2 B2B_2

\vdots

ANA_N BNB_N

出力

高橋君が現在持っている硬貨を用いてちょうど XX 円を支払うことができる場合は Yes を、 できない場合は No を出力せよ。

2 19
2 3
5 6
Yes

高橋君は 22 円硬貨を 33 枚、55 円硬貨を 66 枚持っています。 このうち、22 円硬貨を 22 枚、55 円硬貨を 33 枚用いることでちょうど 2×2+5×3=192\times 2+5\times 3=19 円を支払うことができます。 よって、Yes を出力します。

2 18
2 3
5 6
No

持っている硬貨をどのように組み合わせてもちょうど 1818 円を支払うことはできません。 よって、No を出力します。

3 1001
1 1
2 1
100 10
Yes

11 枚も使用しない硬貨が存在しても構いません。