[ABC014B] 価格の合計

题面翻译

读入两个数n,m。

将m化为二进制。

接着读入n个数字，对于第i个数字，如果m的二进制从低位向高位的第i位是1，答案加上该数字，否则不管。

最后别忘回车

感谢@da32s1da 提供的翻译

题目描述

あなたは買い物をしていて，商品リストからいくつかの商品を選んだ．そして今，その商品の価格を合計しようとしている．

ところで，とある集合の任意の部分集合を $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

样例输入 #1

4 5
1 10 100 1000

样例输出 #1

101

样例 #2

样例输入 #2

20 1048575
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

样例输出 #2

210

样例 #3

样例输入 #3

4 0
1000 1000 1000 1000

样例输出 #3

0

提示

Sample Explanation 1

$n$ と $X$ は問題文中の説明で用いた値である．部分集合は$\{商品0,商品2\}$であるので，$1+100=101$となる．

Sample Explanation 2

$X$ の $2$ 進表現は$11111111111111111111$($20$個の$1$が並んでいる)であるので，部分集合は全商品を含んでいる．

Sample Explanation 3

部分集合が空集合であることもある．