ADAMOLD - Ada and Mold


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.

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

hide comments
tiger_1999: 2020-05-07 13:41:40

we must use all the seprator or we can use any no of seprator ?

sachin2405: 2020-01-15 19:04:14

how to do this question any hint?

chandu_chegu48: 2019-12-04 04:43:52

getting time limit exceed in 15th test case @morass help me

magicarp: 2018-05-30 02:26:22

Awesome problem. Thank you @morass.

enzymii: 2017-12-26 12:40:03

The same code. C++ got TLE. But C++14 got AC.

Last edit: 2017-12-26 13:06:01
shubham_001: 2017-10-28 11:05:45

Thanks @morass for helping , such a nice guy, "Good day to you too" :p

morass: 2017-10-21 09:49:28

@shubham_001: Good day to you .. I don't thinks so =)

shubham_001: 2017-10-21 08:28:52

would O(kn^2) be sufficient?

wisfaq: 2017-10-15 13:58:42

Thanks

Last edit: 2017-10-15 14:17:53
morass: 2017-10-15 12:51:27

@wisfaq: Good day to you. No, you don't have use all separators, you only have to minimize the answer :))


Added by:Morass
Date:2017-10-15
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All