/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君は N 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1\leq i\leq N について A_i 円硬貨を B_i 枚持っています。
高橋君が現在持っている硬貨を用いて、（お釣りが出ないように）ちょうど X 円を支払うことができるか判定してください。
制約
- 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 はすべて異なる。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
高橋君が現在持っている硬貨を用いてちょうど X 円を支払うことができる場合は Yes を、
できない場合は No を出力せよ。
入力例 1
2 19 2 3 5 6
出力例 1
Yes
高橋君は 2 円硬貨を 3 枚、5 円硬貨を 6 枚持っています。
このうち、2 円硬貨を 2 枚、5 円硬貨を 3 枚用いることでちょうど 2\times 2+5\times 3=19 円を支払うことができます。
よって、Yes を出力します。
入力例 2
2 18 2 3 5 6
出力例 2
No
持っている硬貨をどのように組み合わせてもちょうど 18 円を支払うことはできません。
よって、No を出力します。
入力例 3
3 1001 1 1 2 1 100 10
出力例 3
Yes
1 枚も使用しない硬貨が存在しても構いません。
Score : 400 points
Problem Statement
Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.
Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.
Constraints
- 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 are pairwise distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print Yes if Takahashi can pay exactly X yen with the coins he currently has;
print No otherwise.
Sample Input 1
2 19 2 3 5 6
Sample Output 1
Yes
Takahashi has three 2-yen coins and six 5-yen coins.
He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen.
Thus, Yes should be printed.
Sample Input 2
2 18 2 3 5 6
Sample Output 2
No
There is no combination of the coins that he can use to pay exactly 18 yen.
Thus, No should be printed.
Sample Input 3
3 1001 1 1 2 1 100 10
Sample Output 3
Yes
He need not use all kinds of coins.