Maximized Array Sum with Cyclic Bit Shifts

Given n 32-bit integers \(A_i\) and an integer m representing the maximum number of operations allowed, you can perform at most m operations. In each operation, you may select any one number and perform a cyclic left shift by one bit.

A cyclic left shift on a 32-bit number \(x\) is defined as:

[ \text{LeftRotate}(x,1)= ((x \ll 1) ;|; (x \gg 31)) ;&; (2^{32}-1), ]

For example, for an 8-bit number \(10010010_2\):

• After 1 shift: \(00100101_2\)
• After 2 shifts: \(01001010_2\)

You may perform at most m such operations (applied in total across all numbers). For each number, you choose a number of operations (possibly zero, up to 31) to apply a cyclic left shift repeatedly. Note that performing r operations on a number is equivalent to a cyclic left shift by r positions. The goal is to maximize the sum of all n numbers after performing no more than m operations in total.

Hint: For each number \(A_i\), precompute its value after 0 to 31 cyclic left shifts. Then, the improvement for applying \(r\) shifts on \(A_i\) is \(\Delta = \text{LeftRotate}(A_i, r) - A_i\). You may choose one option (with its corresponding cost \(r\) and benefit \(\Delta\)) for each number, subject to the constraint that the total cost does not exceed m. This is a grouped knapSack problem.

inputFormat

The input consists of two lines:

1. The first line contains two integers n and m (\(1 \le n \le 1000\), \(0 \le m \le 1000\)).
2. The second line contains n space-separated integers \(A_1, A_2, \ldots, A_n\) (each treated as a 32-bit unsigned integer).

outputFormat

Output a single integer: the maximum possible sum of the n numbers after performing at most m cyclic left shift operations.

sample

3 2
1 2 4

19