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 bloomvalue). The more vegetable is in the furrow the bigger risk of mold there is. More specificaly the moldvalue can be obtained as sum of xor of all pairs of vegetable's bloomvalues.
Ada has bought a few wooden separators which could possibly reduce the moldvalue. It works in following manner: she can put the separators between some plants, dividing the furrow into multiple segments. The moldvalue will then becomes the sum of moldvalues of all the segments (independently). Can you find the minimal possible moldvalue?
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^{9}, the bloomvalues of vegetable.
Output
Output the minimal possible moldvalue.
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
karankaira:
20200913 11:31:49
This will be done with MCM ,right?? 

tiger_1999:
20200507 13:41:40
we must use all the seprator or we can use any no of seprator ? 

sachin2405:
20200115 19:04:14
how to do this question any hint? 

chandu_chegu48:
20191204 04:43:52
getting time limit exceed in 15th test case @morass help me 

magicarp:
20180530 02:26:22
Awesome problem. Thank you @morass. 

enzymii:
20171226 12:40:03
The same code. C++ got TLE. But C++14 got AC. Last edit: 20171226 13:06:01 

shubham_001:
20171028 11:05:45
Thanks @morass for helping , such a nice guy, "Good day to you too" :p 

morass:
20171021 09:49:28
@shubham_001: Good day to you .. I don't thinks so =) 

shubham_001:
20171021 08:28:52
would O(kn^2) be sufficient? 

wisfaq:
20171015 13:58:42
Thanks Last edit: 20171015 14:17:53 
Added by:  Morass 
Date:  20171015 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 