题目描述
小明创造了一个函数 $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, \dots, a_n\}$,他想知道,在这个数组中选择最多 $m$ 个不相交的区间,将这些区间内的数进行二进制数位翻转(将 $a_i$ 变为 $f(a_i)$)后,整个数组的和最大是多少?
输入格式
输入共 $2$ 行。
第一行为两个正整数 $n, m$。
第二行为 $n$ 个由空格分开的整数 $a_1, a_2, \dots, a_n$。
样例输入 #1
5 3
11 12 13 14 15
样例输入 #2
6 2
23 8 11 19 16 35
提示
#### 【样例说明 1】
只翻转 $a_1$,和为 $13 + 12 + 13 + 14 + 15 = 67$。
#### 【样例说明 2】
翻转区间 $[a_3, a_4]$ 和 $[a_6]$,和为 $23 + 8 + 13 + 25 + 16 + 49 = 134$。
#### 【评测用例规模与约定】
对于 $20\%$ 的评测用例,保证 $n, m \le 20$。
对于 $100\%$ 的评测用例,保证 $n, m \le 1000$,$0 \le a_i \le 10^9$。
来源
第十五届蓝桥杯大赛软件类国赛C/C++大学B组