Maximizing Array Sum with Binary Digit Reversal

Little Ming invented a function \( f(x) \) which reverses the binary digits of \( x \) (without any leading zeros). For example, since \( 11 = (1011)_2 \), we have \( f(11) = 13 \) because reversing \( 1011 \) gives \( 1101 \) which equals \( 13 \). Some other examples include \( f(3)=3 \), \( f(0)=0 \), and \( f(2)=f(4)=f(8)=1 \) (since, e.g., \( 2 = (10)_2 \) and its reverse \( 01 \) is interpreted as \( 1 \)).

You are given an integer array \( \{a_1,a_2,\dots,a_n\} \) of length \( n \). You are allowed to choose at most \( m \) non-overlapping intervals (contiguous subarrays) of the array. For each chosen interval, you apply the transformation \( a_i \rightarrow f(a_i) \) for every \( i \) in the interval. Your task is to maximize the total sum of the array after performing these operations.

Observation: For each element, define the improvement \( \delta_i = f(a_i)-a_i \). Then, your goal is to choose at most \( m \) disjoint intervals such that the sum of \( \delta_i \) over all elements in those intervals is maximized. Note that it may be optimal to not choose some intervals if they would decrease the sum.

Input Constraints: The first line contains two integers \( n \) and \( m \). The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \).

Output: Output a single integer representing the maximum possible total sum after performing the operations.

inputFormat

The input consists of two parts:

• The first line contains two integers \( n \) and \( m \) (the length of the array and the maximum number of intervals you can choose).
• The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \).

outputFormat

Output a single integer: the maximum total sum of the array after applying up to \( m \) non overlapping interval operations.

sample

5 2
11 3 0 2 8

26