数位翻转

题目描述

小明创造了一个函数 $f(x)$ 用来翻转 $x$ 的二进制的数位（无前导 $0$）。比如$f(11) = 13$，因为 $11 = (1011)2$，将其左右翻转后，变为 $13 = (1101)2$；再比如$f(3) = 3，f(0) = 0，f(2) = f(4) = f(8) = 1$ 等等。

小明随机出了一个长度为 $n$ 的整数数组 ${a_1, a_2, ..., a_n}$，他想知道，在这个数组中选择最多 $m$ 个不相交的区间，将这些区间内的数进行二进制数位翻转（将$a_i$ 变为 $f(a_i)$）后，整个数组的和最大是多少？

输入格式

输入共 $2$ 行。

第一行为两个正整数 $n, m$。

第二行为 $n$ 个由空格分开的整数 $a_1, a_2, ..., a_n$。

输出格式

输出共 $1$ 行，一个整数表示答案。

样例 #1

样例输入 #1

5 3
11 12 13 14 15

样例输出 #1

67

提示

【样例说明 1】只翻转 $a_1$，和为 $13 + 12 + 13 + 14 + 15 = 67$。

再比如：

【样例输入 2】$6$ $223$ $8$ $11$ $19$ $16$ $35$

【样例输出 2】$134$

【样例说明 2】翻转区间 $[a3, a4]$ 和 $[a6]$，和为 $23 + 8 + 13 + 25 + 16 + 49 = 134$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，保证 $n, m ≤ 20$。

对于 $100\%$ 的评测用例，保证 $n, m ≤ 1000，0 ≤ a_i ≤ 10^9$。