P7335 [JRKSJ R1] XOR

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.**

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 one non-negative integer in one line, which is the maximum value of the expression.

### 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 | $10$ | | $4$ | $1500$ | None | $15$ | | $5$ | $2000$ | None | $15$ | | $6$ | $2500$ | None | $20$ | | $7$ | $3000$ | None | $25$ | Translated by ChatGPT 5