Maximize Weighted Popcount Sum

You are given n integers \(a_1, a_2, \dots, a_n\). Your task is to choose n non‐negative integers \(b_1, b_2, \dots, b_n\) satisfying

[ 0 \le b_1 < b_2 < \cdots < b_n \le m, ]

so as to maximize the value

[ S = a_1\times f(b_1) + a_2\times f(b_2) + \cdots + a_n\times f(b_n), ]

where \(f(x)\) is defined as the number of \(1\)s in the binary representation of \(x\) (i.e. its popcount).

Note: There may be negative values among the \(a_i\). In such cases it might be optimal to assign numbers with lower popcount to those indices.

inputFormat

The first line of input contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of integers and \(m\) is the maximum allowed value for \(b_n\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer, representing the maximum possible value of \(S = \sum_{i=1}^n a_i \times f(b_i)\) achievable under the constraints.

sample

2 5
1 2

6