Chef and Bitwise OR Operation

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef studies very well in his University. There is only one professor who doesn't want to give him the highest grade, A. Chef has had a long argument with him, and eventually they agreed, that if Chef solves an algorithmic problem, he gets the highest grade. After looking at the problem, he realized he can't solve it. Once again, he approached Codechef admins for help, and once again we decided to put it off and pass on the task to you. Please, help him (and us)!
Problem description
You are given an array A of integers and an integer K. Your goal is to divide the array into K consecutive disjoint nonempty groups, so that any array element belongs to exactly one group.
Each group can be specified by two integers L and R (L ≤ R) with the meaning that the group contains all the elements from the L^{th} to the R^{th} one (both inclusive) in the given array. The cost of such a group equals to the value of bitwise OR of all elements in the group.
The cost of array for some particular group division equals to the sum of costs for all the groups. You have to find the maximal achievable cost of the given array.
You can read more about bitwise OR operation here
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and K denoting the number of elements in the array and number of groups, respectively.
The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the given array.
Output
For each test case, output a single line, containing the maximal achievable cost of the array.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 5000
 1 ≤ K ≤ N
 0 ≤ A_{i} ≤ 2^{30}
 Subtask 1(15 points): 1 ≤ N ≤ 100
 Subtask 2(35 points): 1 ≤ N ≤ 1000
 Subtask 3(50 points): 1 ≤ N ≤ 5000
 The time limit for the first and the second subtask is 1 second. The time limit for the third subtask is 10 seconds.
Example
Input: 4 3 2 1 2 2 4 3 1 2 3 4 2 2 1 2 11 4 66 152 7 89 42 28 222 69 10 54 99 Output: 5 10 3 704
Explanation
Example case 1. The optimal group division is the following one: put the first two numbers to the first group, and the next one into the second. This way, you will obtain the cost of the array equal to (1 OR 2) + 2 = 3 + 2 = 5.
Example case 2. The first two integers should be in the first group, the third one should be in the second group, the fourth one should be in the third group. This way, we will obtain a cost of an array equal to (1 OR 2) + 3 + 4 = 3 + 3 + 4 = 10.
Example case 3. Each number will be in its' own group. So, we obtain a cost of 1 + 2 = 3.
Example case 4. Try to figure out yourself.
Author:  furko 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFAOR 
Tags  dynamicprogramming, easymedium, furko, ltime25 
Date Added:  13062015 
Time Limit:  1  10 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions