22688_CollatzProble

If integer n is even, f(n)=n/2 , otherwise(n is odd), f(n)=3n+1. Specially, f(1)=1 .

Further more, let us define a function g:

Collatz Problem (3N+1 Problem):

For all integers N ( N ≥ 1 ), there is a number K₀ that g(N,K)=1 when K ≥ K₀ ?

Collatz problem is too hard, and it's still unsolved now. Of course, you don’t have to solve it today. The problem you have to solve now is much easier:

Assume that each number has a positive value, you have to select no more than M numbers ( x_1, ..., x_M ) from [1, N] that any two of them ( x_i, x_j ( 1 ≤ i, j ≤ M ) ) obey the following rule:

for any k,   x_j ≠ g(x_i, k)  and  x_i ≠ g(x_j, k)

Finally, output the maximum sum of the value of the numbers you selected.

The first line of the input is a positive integer C, denoting the number of test cases followed.

The first line of each test case is two positive integers N ( 1 ≤ N ≤ 100 ) and M. After that, N lines follow. The i-th ( 1 ≤ i ≤ N ) line contains the value of number i ( 1 ≤ value[i] ≤ 500 ).

The output should consist of C lines, one line for each test case, only containing one number that represents the maximum sum of the value of the numbers you selected. No redundant spaces are needed.

1
3 2
10
15
25

25

In the sample, g(3,6)=2, g(3,7)=1, g(2,1)=1. So, you can select only one number, 1 or 2 or 3. Of course, you will select 3, whose value is maximal.