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 ≤ Ai ≤ 109, the bloom-values of vegetable.

### Output

Output the minimal possible mold-value.

```6 1
1 2 3 4 5 6
```

```12
```

```4 3
5 3 5 3
```

```0
```

```7 2
5 3 5 3 5 3 4
```

```24
```

### Example Input 3

```9 4
1 2 3 4 5 6 7 666 1024
```

```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
```