As you might already know, Ada the Ladybug is a farmer. She has a long furrow in which she grows vegetable (while each vegetable is indentified by a bloom-value). The more vegetable is in the furrow the bigger risk of mold there is. More specificaly the mold-value can be obtained as sum of xor of all pairs of vegetable's bloom-values.

Ada has bought a few wooden separators which could possibly reduce the mold-value. It works in following manner: she can put the separators between some plants, dividing the furrow into multiple segments. The mold-value will then becomes the sum of mold-values of all the segments (independently). Can you find the minimal possible mold-value?

Input

The first line of input containts two integers N, K: 1 ≤ K < N ≤ 5000, the length of furrows and the number of separators.

The next lines will contain N numbers 0 ≤ A_i ≤ 10⁹, the bloom-values of vegetable.

Output

Output the minimal possible mold-value.

Example Input

6 1
1 2 3 4 5 6

Example Output

12

Example Input 1

4 3
5 3 5 3

Example Output 1

0

Example Input 2

7 2
5 3 5 3 5 3 4

Example Output21

24

Example Input 3

9 4
1 2 3 4 5 6 7 666 1024

Example Output 3

8

Example Input 4

30 8
629470789 417274987 617986533 841737683 297969800 432044389 708142005 156958893 499363651 434034331 176735187 525172817 747109631 949700868 259681519 357968078 818249370 456939952 450487335 529013233 327250536 90354657 643708145 141755216 656041628 661580907 204072850 469709611 834069223 681347499

Example Output 4

16154467281