题目描述

你正在购物，从商品列表中选取了一些商品。现在，你需要计算这些商品的总价格。

顺便一提，有一种方法可以用二进制来表示某个集合的任意子集，这种方法常用于用 for 循环枚举所有子集（组合）时。

• 假设有 $n$ 个商品，分别为商品 $0$、商品 $1$、……、商品 $n-1$。请注意，商品编号从 $0$ 开始。

• 用十进制整数 $X$ 表示一个子集，其 $n$ 位二进制表示为 $b_{n-1}b_{n-2}\ldots b_1b_0$。其中 $b_0$ 是最低位，$b_{n-1}$ 是最高位。请注意，这种表示允许前导 $0$。

然后，利用这个整数 $X$ 的二进制表示，可以如下定义一个子集：

• 如果 $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$ 的二进制表示中，第 $k$ 位（$0\leq k\leq n-1$）为 $1$ 时，表示包含第 $k$ 个商品。是否包含某一位可以通过大多数编程语言轻松判断，请自行查阅相关方法。

你的任务是：给定商品数量、每个商品的价格，以及表示子集的十进制整数 $X$，计算该子集中所包含商品的总价格。

※本题虽然与此无关，但通过上述方法可以用 $0$ 到 $2^n-1$ 的连续整数表示大小为 $n$ 的集合的所有子集（包括空集），在需要全枚举时可以加以应用。

输入格式

输入通过标准输入给出，格式如下：

$n$ $X$ $a_0$ $a_1$ $a_2$ ... $a_{n-1}$

• 第 $1$ 行包含商品数量 $n\ (1\leq n\leq 20)$ 和表示商品子集的十进制整数 $X\ (0\leq X\leq 2^n-1)$，两者以空格分隔。

• 第 $2$ 行包含商品 $0$ 到 $n-1$ 的价格 $a_0,a_1,\ldots,a_{n-1}\ (0\leq a_0,a_1,\ldots,a_{n-1}\leq 1,000)$，按顺序以空格分隔。

输出格式

• 输出子集中所包含商品的总价格，输出一行，末尾需换行。

输入输出样例 #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

说明/提示

样例解释 1

$n$ 和 $X$ 与题目描述中的示例一致。子集为 $\{商品0, 商品2\}$，因此 $1+100=101$。

样例解释 2

$X$ 的二进制表示为 $11111111111111111111$（共 $20$ 个 $1$），因此子集包含所有商品。

样例解释 3

子集也可能为空集。

由 ChatGPT 4.1 翻译