6727: 蜈蚣

内存限制:125 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

一群人在山上遇见了一条蜈蚣。在一条山路的转角处,WYH 发现了一条有中指一样粗的有 $N$ 节的蜈蚣。这只蜈蚣马上就吸引了 HKE 的眼球,HKE 深深地爱上了这条魔性的蜈蚣。它的很多对足在前进的时候像波浪一样,颇是有毒。
但是,热爱解剖动物的 MZL 却准备把蜈蚣切了。HKE 很失落,于是 MZL 承诺不会完全肢解它,只把它的 $N$ 节切成 $M$ 段,每一段包含原蜈蚣完整的一节或多节。
HKE 看到他心爱的蜈蚣会切掉是会觉得恶心的。蜈蚣的每一节都有一个权值 $W_i$,切下来的一段 $(W_i, W_{i + 1}, \ldots, W_j)$ 带给 HKE 的恶心值是 $W_i \mathbin{\mathrm{xor}} W_{i + 1} \mathbin{\mathrm{xor}} \cdots \mathbin{\mathrm{xor}} W_j$,这里的 $\mathbin{\mathrm{xor}}$ 代表按位异或操作。邪恶的 LJC 希望 HKE 受到的总恶心值 —— 也就是每一段子蜈蚣带给 HKE 的恶心值的和最大,请你求出 HKE 的最大恶心值。
(注:按位异或,其运算符号在 Pascal 中为 `xor`,在 C++ 中为 `^` 或 `xor`;请注意加法与异或运算的优先级先后顺序)

输入格式

第一行,两个整数 $N, M$,表示蜈蚣长 $N$ 节,切成 $M$ 段;第二行 $N$ 个整数用空格分开,表示蜈蚣每一节的权值 $W_1, W_2, \ldots, W_n$。

输出格式

一个整数表示最大恶心值。

输入样例 复制

5 3
1 2 3 4 5

输出样例 复制

15

数据范围与提示

**【样例解释 \#1】**

第一段的恶心值为 $1 \mathbin{\mathrm{xor}} 2 = 3$。

第二段的恶心值为 $3 \mathbin{\mathrm{xor}} 4 = 7$

第三段的恶心值为 $5$

总恶心值为 $3 + 7 + 5 = 15$。此时为最优解。

**【数据范围】**

对于 $30 \%$ 的数据,$1 \le N \le 100$,$1 \le M \le 10$;

对于 $100 \%$ 的数据,$1 \le N \le 1000$,$1 \le M \le 100$,保证结果在 $2^{30} - 1$ 内;