Problem Description

Xiaoming created a function $f(x)$ to reverse the binary digits of $x$ (with no leading $0$). For example, $f(11) = 13$, because $11 = (1011)_2$, and after reversing it left to right, it becomes $13 = (1101)_2$. Another example: $f(3) = 3$, $f(0) = 0$, and $f(2) = f(4) = f(8) = 1$, and so on.

Xiaoming randomly generated an integer array $\{a_1, a_2, \cdots, a_n\}$ of length $n$. He wants to know: in this array, if you choose at most $m$ disjoint intervals and reverse the binary digits of the numbers inside these intervals (change $a_i$ to $f(a_i)$), what is the maximum possible sum of the entire array?

Input Format

The input has $2$ lines.

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

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ separated by spaces.

Output Format

Output $1$ line containing one integer, which is the answer.

5 3
11 12 13 14 15

67

6 2
23 8 11 19 16 35

134

Hint

[Sample Explanation 1]

Flip only $a_1$, and the sum is $13 + 12 + 13 + 14 + 15 = 67$.

[Sample Explanation 2]

Flip intervals $[a_3, a_4]$ and $[a_6]$, and the sum is $23 + 8 + 13 + 25 + 16 + 49 = 134$.

[Constraints]

For $20\%$ of the testdata, it is guaranteed that $n, m \le 20$.
For $100\%$ of the testdata, it is guaranteed that $n, m \le 1000$, and $0 \le a_i \le 10^9$.

Translated by ChatGPT 5