Problem Description

You are shopping and have selected several items from a list. Now, you are trying to sum up the prices of these items.

There exists a method to represent any subset of a given set using binary numbers, which can be used when enumerating all subsets (combinations) with a for loop, etc.

• Suppose there are $ n $ items, labeled as item $ 0 $, item $ 1 $, ..., item $ n-1 $. Note that the indices start from $ 0 $.
• Let the decimal integer $ X $ represent a subset, and its $ n $-digit binary representation be $ b_{n-1}b_{n-2}...b_1b_0 $. $ b_0 $ is the least significant bit and $ b_{n-1} $ is the most significant bit. Note that leading zeros are allowed.

Using the binary representation of this integer $ X $, a subset can be defined as follows:

• If $ b_0 = 1 $, the set includes item $ 0 $; if $ b_0 = 0 $, the set does not include item $ 0 $.
• If $ b_1 = 1 $, the set includes item $ 1 $; if $ b_1 = 0 $, the set does not include item $ 1 $.
• ...
• If $ b_{n-1} = 1 $, the set includes item $ n-1 $; if $ b_{n-1} = 0 $, the set does not include item $ n-1 $.

For example, when $ n = 4 $ and $ X = 5 $, $ b = 0101 $, and the subset is $\{item 0, item 2\}$. Simply put, if the $ k $-th bit (where $0 \leq k \leq n-1$) is set in the binary representation of $ X $, the subset includes the $ k $-th item. Whether a bit is set or not can be easily determined in many programming languages, so you may want to look it up.

Your task is, given the number of items, the price of each item, and the decimal integer $ X $ representing a subset, to sum the prices of the items included in the subset.

*Although not directly related to this problem, representing subsets as described allows all subsets (including the empty set) of a set of size $ n $ to be represented by consecutive integers from $ 0 $ to $ 2^n - 1 $, which is useful when enumerating all subsets.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains the number of items $n\ (1 \leq n \leq 20)$ and the decimal integer $X\ (0 \leq X \leq 2^n - 1)$ representing a subset of items, separated by spaces.
• The second line contains the prices of items $ 0 $ to $ n-1 $: $a_0, a_1, ..., a_{n-1}\ (0 \leq a_0, a_1, ..., a_{n-1} \leq 1,000)$, in order, separated by spaces.

Output Format

• Output the sum of the prices of the items included in the subset on a single line. Include a newline at the end of the output.

Sample Input and Output

Sample Input #1

4 5
1 10 100 1000

Sample Output #1

101

Sample Input #2

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

Sample Output #2

210

Sample Input #3

4 0
1000 1000 1000 1000

Sample Output #3

0

Notes/Hints

Sample Explanation 1

$ n $ and $ X $ are the values used in the problem description. The subset is $\{item 0, item 2\}$, so the sum is $ 1 + 100 = 101 $.

Sample Explanation 2

The binary representation of $ X $ is $ 11111111111111111111 $ (20 ones in a row), so the subset includes all items.

Sample Explanation 3

The subset can also be the empty set.

见题面 Input 部分

见题面 Output 部分