#21088. 密集恐惧症

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: renjiaxin

题目描述

咪码有严重的密集恐惧症,小强为了治疗咪码的恐惧心理,决定以毒攻毒,拿了一个有长度为 N 扎满小洞的木板,准备把他砍成M节(每节长度是一个整数),这个小木板每个单位长度都有一个小洞的密集值 W_i ,从i到j被砍下来的一节 (W_i,W_{i+1}...,W_{j}) 的密集值为 W_i \land W_{i+1} \land ..... \land W_{j} , 其中 \land 表示异或。为了达到以毒攻毒的最好效果,小强需要知道这个木板能砍出来的小板的密集值之和最大是多少。

输入格式

第一行,两个整数 N, M

第二行,N个整数用空格分开,表示每单位木板的密集值 W_1, W_2, \ldots, W_n

输出格式

一行,表示所有小木板密集值的和的最大值

样例

5 3
2 2 3 4 5

12

数据范围与提示

第一段的密集值为 2 xor 2 = 0

第二段的密集值为 3 xor 4 = 7

第三段的密集值为 5

总密集值为 0 + 7 + 5 =12。

此时为最优解。

对于30%的数据,1<= N <= 100, 1<= M <= 10,

对于100%的数据,1<= N <= 1000, 1<= M <= 100

保证结果在int的范围内。