/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は N 種類の薬品を持っています。i 番目の薬品には通常モードと加熱モードの 2 つの使い方があり、通常モードで使うと A_i mL、加熱モードで使うと B_i mL の溶液が得られます。
高橋君はこれらの薬品の中から、いくつか（0 個でもよい）を選び、選んだ各薬品について通常モードと加熱モードのどちらで使うかを独立に決めます。各薬品は最大 1 回しか使えません。選んだ薬品から得られる溶液の量の合計がちょうど K mL となるようにできるかどうかを判定してください。
可能な場合は 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
- 1 行目には、薬品の種類数を表す整数 N と、目標の溶液量を表す整数 K が、スペース区切りで与えられる。
- 続く N 行にわたって、各薬品の情報が与えられる。
- 1 + i 行目には、i 番目の薬品の通常モードでの生成量 A_i と、加熱モードでの生成量 B_i が、スペース区切りで与えられる。
出力
選んだ薬品から得られる溶液の量の合計がちょうど K mL となるようにできるならば Yes を、そうでなければ No を 1 行で出力せよ。
入力例 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
Score : 433 pts
Problem Statement
Takahashi has N types of chemicals. The i-th chemical has two modes of use: normal mode and heated mode. Using it in normal mode yields A_i mL of solution, and using it in heated mode yields B_i mL of solution.
From these chemicals, Takahashi selects some (possibly zero) of them, and for each selected chemical, independently decides whether to use it in normal mode or heated mode. Each chemical can be used at most once. Determine whether it is possible for the total amount of solution obtained from the selected chemicals to be exactly K mL.
If it is possible, output Yes; if it is impossible, output No.
Constraints
- 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}
- All input values are integers.
Input
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
- The first line contains an integer N representing the number of types of chemicals, and an integer K representing the target amount of solution, separated by a space.
- The following N lines provide information about each chemical.
- The (1 + i)-th line contains the amount produced in normal mode A_i and the amount produced in heated mode B_i for the i-th chemical, separated by a space.
Output
If it is possible for the total amount of solution obtained from the selected chemicals to be exactly K mL, output Yes; otherwise, output No on a single line.
Sample Input 1
3 10 3 5 4 6 1 8
Sample Output 1
Yes
Sample Input 2
2 5 2 4 6 8
Sample Output 2
No
Sample Input 3
8 57 11 14 7 10 9 15 13 20 17 18 6 16 8 12 5 21
Sample Output 3
Yes
Sample Input 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
Sample Output 4
Yes
Sample Input 5
1 0 1 100000000000000
Sample Output 5
Yes