Mateusz loves pop music. It is relaxing, great for dancing, and even helps with programming. However, all these advantages require good synchronization of the melody with the beat.

Mateusz has just created a new melody and intends to match it with good beats. The melody lasts $n$ seconds, and some of its moments can be much better than others. The quality of the $i$-th second of the melody is described by an integer $a_i$ (possibly negative), and a non-negative integer bit-amplification coefficient $b_i$ must be chosen for it.

The coefficient amplifies this second $C(b_i)$ times, where $C(b_i)$ denotes the number of set bits (population count) in the binary representation of the number $b_i$.

• For example, choosing $b_i = 13$ gives a threefold amplification of the $i$-th second of the melody, because the binary representation of the number 13 is 1101 and it contains three set bits.

The final quality of the entire song can be written as: $$a_1 \cdot C(b_1) + a_2 \cdot C(b_2) + \dots + a_n \cdot C(b_n).$$

Everyone likes songs with increasing bit amplification, and Mateusz is no exception. The bit coefficients $b_i$ must form an increasing sequence of non-negative integers with a certain upper limit $m$: $$0 \le b_1 < b_2 < \dots < b_n \le m.$$

Mateusz's goal is to choose the bit coefficients in such a way as to maximize the final quality of the song. What is the maximum value he can obtain?

Input

The first line of input contains two integers $n, m$ ($1 \le n \le 200, n - 1 \le m \le 10^{18}$), representing the duration of the song in seconds and the upper limit on the bit coefficients.

The second line of input contains $n$ integers $a_1, \dots, a_n$ ($-10^{14} \le a_i \le 10^{14}$), representing the qualities of successive seconds of the melody.

Output

The output should contain a single integer – the maximum possible final quality of the song.

Examples

Input 1

3 5
2 -1 3

Output 1

9

Input 2

3 2
1 1 -1

Output 2

0

Note

Explanation of the first example: The melody consists of three seconds with qualities 2, $-1$, 3 respectively. Note that the quality of a second can be negative! The optimal sequence $b$ is $b_1 = 3, b_2 = 4, b_3 = 5$. Then we get: $$a_1 \cdot C(b_1) + a_2 \cdot C(b_2) + a_3 \cdot C(b_3) = 2 \cdot C(3) + (-1) \cdot C(4) + 3 \cdot C(5) = 2 \cdot 2 + (-1) \cdot 1 + 3 \cdot 2 = 9$$

*In other words, $C(b_i)$ is the number of ones in the binary representation of the number $b_i$.