P10911 [Lanqiao Cup 2024 National B] Digit Flip

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?

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 $1$ line containing one integer, which is the answer.

**[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