问题描述

小明创造了一个函数 $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$ 行，一个整数表示答案。

5 3
11 12 13 14 15

67

6 2
23 8 11 19 16 35

134

样例说明

• 样例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≤20$。

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