Description

Given $n$ integers $a_{1..n}$, find $n$ non-negative integers $b_{1..n}$ to maximize the value of $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$, where $\operatorname{f(x)}$ is the number of $1$ bits in the binary representation of $x$.

The $n$ non-negative integers $b_{1..n}$ you find must satisfy $0\le b_1<b_2<...<b_n\le m$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers $a_1, a_2, ..., a_n$.

Output Format

Output one integer in one line, which is the maximum value of $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$.

3 5
2 -1 3

9

Hint

For $100\%$ of the testdata, $1\le n\le 200$, $n-1\le m\le 10^{18}$, and $|a_i|\le 10^{14}$.

Explanation

Let $b_1=3, b_2=4, b_3=5$. Then the answer is $2\times 2+(-1)\times 1+3\times 2=9$.

Translated by ChatGPT 5