[JRKSJ R1] 异或
题目描述
给你 $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$ 行输出一个非负整数，代表这个式子的最大值。
输入输出样例
输入样例 #1
6 3
2 1 3 4 4 4输出样例 #1
15输入样例 #2
7 2
3 4 5 6 7 8 9输出样例 #2
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$ | 无 | $10$ |
| $4$ | $1500$ | 无 | $15$ |
| $5$ | $2000$ | 无 | $15$ |
| $6$ | $2500$ | 无 | $20$ |
| $7$ | $3000$ | 无| $25$ |
#### 样例 1 解释
序列的三个区间分别为:
$$2,1,[3,4],[4],[4]$$
所得的三个区间的异或和之和为 $7+4+4=15$.