题目描述

给你 $n,k$ 和序列 $a_{1,2\dots n}$，选出 $k$ 个不交区间 $[l_i,r_i]\subseteq[1,n]$，求出

$$\max_{l_i,r_i}\sum_{i=1}^k\bigoplus_{j=l_i}^{r_i}a_j $$

式中 $\oplus$ 表示二进制异或运算。

保证数据随机。

输入格式

输入共 $2$ 行。
第 $1$ 行输入两个数 $n,k$。
第 $2$ 行输入 $n$ 个非负整数代表序列 $a$。

输出格式

$1$ 行输出一个非负整数，代表这个式子的最大值。

6 3
2 1 3 4 4 4

15

7 2
3 4 5 6 7 8 9

24

提示

对于 $100\%$ 的数据，$1\le k\le n\le 3000$，$0\le a_i\le 10^{9}$。保证数据随机。

本题采用捆绑测试。

$\text{Subtask}$	$n\le$	特殊性质	分值
$1$	$30$	$k\le3$	$5$
$2$	$500$	$a_i\le10^7$	$10$
$3$	$1000$	无
$4$	$1500$		$15$
$5$	$2000$
$6$	$2500$		$20$
$7$	$3000$		$25$

样例 1 解释

序列的三个区间分别为:

$$2,1,[3,4],[4],[4]$$

所得的三个区间的异或和之和为 $7+4+4=15$.