問題文
您正在购物并从商品列表中选择一些商品。现在我们正在尝试总结产品的价格。
顺便说一句,如果某个集合的任何子集是 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
4 5 1 10 100 1000
出力例1
101
n 和 X 是问题文本中的解释中使用的值。子集是\{商品0,商品2\},所以1+100=101变为。
入力例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
X 的 2 十六进制表示为11111111111111111111(20的1已排列),因此该子集包括所有产品。
入力例3
4 0 1000 1000 1000 1000
出力例3
0
子集可以是空集。