5461：AT_abc014_2 [ABC014B] 価格の合計
文件提交：无需freopen
内存限制：256 MB
时间限制：2.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：1
解决：0
题目描述
# AT_abc014_2 [ABC014B] 価格の合計
## 题目信息
- 题号：AT_abc014_2
- 标题：[ABC014B] 価格の合計
- 难度：入门
- 标签：进制, 位运算
- 时间限制：2.00s
- 内存限制：256.00MB
- 提交数：1564
- 通过数：862
## 题目翻译
读入两个数n,m。
将m化为二进制。
接着读入n个数字，对于第i个数字，如果m的二进制从低位向高位的第i位是1，答案加上该数字，否则不管。
最后别忘回车
感谢@da32s1da 提供的翻译
## 题目描述
[problemUrl]: https://atcoder.jp/contests/abc014/tasks/abc014_2
あなたは買い物をしていて，商品リストからいくつかの商品を選んだ．そして今，その商品の価格を合計しようとしている．
ところで，とある集合の任意の部分集合を $ 2 $ 進数を用いて表す方法が存在し，forループで全ての部分集合(組み合わせ)を列挙する際などに用いることができる．
- $ n $ 個の商品があり， 商品$ 0 $,商品$ 1 $,..,商品$ n-1 $ があるとする．添字が$ 0 $から始まることに注意せよ．
- 部分集合を表す $ 10 $ 進整数を $ X $ とし，その $ 2 $ 進 $ n $ 桁表現を$ b_{n-1}b_{n-2}...b_1b_0 $とする．$ b_0 $ が最下位ビットで $ b_{n-1} $ が最上位ビットである．先頭の$ 0 $ を許す表現であることに注意せよ．
そして，この整数 $ X $ の $ 2 $ 進表現を用いて，ある部分集合を以下のように定義する．
- $ b_0=1 $ ならば集合は商品$ 0 $ を含み，$ b_0=0 $ ならば集合は商品 $ 0 $ を含まない．
- $ b_1=1 $ ならば集合は商品$ 1 $ を含み，$ b_1=0 $ ならば集合は商品 $ 1 $ を含まない．
- ...
- $ b_{n-1}=1 $ ならば集合は商品 $ n-1 $ を含み，$ b_{n-1}=0 $ ならば集合は商品 $ n-1 $ を含まない．
例えば，$ n=4,X=5 $ のとき， $ b=0101 $ であり，部分集合は $ \{商品0,商品2\} $ である． 簡単にいえば，$ X $の $ 2 $ 進表現において，$ k(0\ ≦\ k\ ≦\ n-1) $ 番目のビットが立っていれば $ k $ 番目のアイテムを含むということである．あるビットが立っているかどうかは，多くのプログラミング言語で容易に判定できるので，各自調べられたい．
あなたの仕事は，商品の数，それぞれの商品の価格，そして部分集合を表す $ 10 $ 進整数 $ X $ が与えられるので，部分集合に含まれる商品の価格を合計することである．
※今回の問題には直接関係は無いが，部分集合を上記のように表現することで，大きさ $ n $ の集合の全ての部分集合(空集合を含む)を$ 0 $ ～ $ 2^n-1 $ の連続した整数で表現できるので，全列挙を行う際には応用するとよい．
## 输入格式
入力は以下の形式で標準入力から与えられる。
> $ n $ $ X $ $ a_0 $ $ a_1 $ $ a_2 $ ... $ a_{n-1} $
- $ 1 $ 行目には，商品の数 $ n\ (1\ ≦\ n\ ≦\ 20) $ と，商品の部分集合を表す $ 10 $ 進整数 $ X\ (0\ ≦\ X\ ≦\ 2^{n}-1) $ が空白区切りで与えられる．
- $ 2 $ 行目には，商品 $ 0 $ ～ $ n-1 $ の商品の価格 $ a_0,a_1,...,a_{n-1}(0\ ≦\ a_0,a_1,...,a_{n-1}\ ≦\ 1,000) $ が順番に空白区切りで与えられる．
## 输出格式
- 部分集合に含まれる商品の価格を合計したものを $ 1 $ 行に出力せよ．出力の末尾に改行をいれること．
## 输入输出样例
### 输入 #1
```text
4 5
1 10 100 1000
```
### 输出 #1
```text
101
```
### 输入 #2
```text
20 1048575
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
```
### 输出 #2
```text
210
```
### 输入 #3
```text
4 0
1000 1000 1000 1000
```
### 输出 #3
```text
0
```
## 说明/提示
### Sample Explanation 1
$ n $ と $ X $ は問題文中の説明で用いた値である．部分集合は$ \{商品0,商品2\} $であるので，$ 1+100=101 $となる．
### Sample Explanation 2
$ X $ の $ 2 $ 進表現は$ 11111111111111111111 $($ 20 $個の$ 1 $が並んでいる)であるので，部分集合は全商品を含んでいる．
### Sample Explanation 3
部分集合が空集合であることもある．