Problem Description

You are given $n$, $k$, and a sequence $a_{1,2\dots n}$. Choose $k$ disjoint intervals $[l_i, r_i] \subseteq [1, n]$, and compute

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

Here, $\oplus$ denotes the bitwise XOR operation.

The testdata is guaranteed to be random.

Input Format

The input has $2$ lines.
The first line contains two integers $n, k$.
The second line contains $n$ non-negative integers representing the sequence $a$.

Output Format

Output one non-negative integer in one line, which is the maximum value of the expression.

6 3
2 1 3 4 4 4

15

7 2
3 4 5 6 7 8 9

24

Hint

Sample 1 Explanation

The three intervals chosen in the sequence are:

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

The sum of XOR values of the three intervals is $7+4+4=15$.

Constraints

For all testdata, it is guaranteed that $1\le k\le n\le 3000$ and $0\le a_i\le 10^{9}$. The testdata is guaranteed to be random.

This problem uses bundled tests.

$\text{Subtask}$	$n\le$	Special Property	Score
$1$	$30$	$k\le3$	$5$
$2$	$500$	$a_i\le10^7$	$10$
$3$	$1000$	None
$4$	$1500$		$15$
$5$	$2000$
$6$	$2500$		$20$
$7$	$3000$		$25$

Translated by ChatGPT 5