Description

At a turn on a mountain path, WYH found a centipede as thick as a middle finger with $N$ segments. This centipede immediately caught HKE's eye, and HKE fell deeply in love with this uncanny centipede. Many pairs of its legs move like waves when it crawls.

However, MZL, who loves dissecting animals, planned to cut the centipede. HKE felt upset, so MZL promised not to dismember it completely, but to cut its $N$ segments into $M$ parts, each part containing one or more consecutive original segments.

HKE feels sick when he sees his beloved centipede being cut. Each segment has a weight $W_i$. The nausea value of a cut part $(W_i, W_{i + 1}, \ldots, W_j)$ is $W_i \mathbin{\mathrm{xor}} W_{i + 1} \mathbin{\mathrm{xor}} \cdots \mathbin{\mathrm{xor}} W_j$, where $\mathbin{\mathrm{xor}}$ denotes the bitwise XOR operation. The evil LJC wants the total nausea value — that is, the sum of the nausea values of all parts — to be as large as possible. Please compute the maximum total nausea value that HKE can suffer.

(Note: For bitwise XOR, the operator is xor in Pascal, and ^ or xor in C++. Please pay attention to the precedence between addition and XOR operations.).

Input Format

The first line contains two integers $N, M$, meaning the centipede has $N$ segments and will be cut into $M$ parts.

The second line contains $N$ integers separated by spaces, representing the weights $W_1, W_2, \ldots, W_N$ of the segments.

Output Format

Output a single integer, the maximum total nausea value.

5 3
1 2 3 4 5

15

Hint

[Sample Explanation #1]

The nausea value of the first part is $1 \mathbin{\mathrm{xor}} 2 = 3$.

The nausea value of the second part is $3 \mathbin{\mathrm{xor}} 4 = 7$.

The nausea value of the third part is $5$.

The total nausea value is $3 + 7 + 5 = 15$. This is optimal.

[Constraints]

For $30\%$ of the testdata, $1 \le N \le 100$, $1 \le M \le 10$.

For $100\%$ of the testdata, $1 \le N \le 1000$, $1 \le M \le 100$, and the result is guaranteed to be within $2^{30} - 1$.

Translated by ChatGPT 5