P5985 [PA 2019] Pop Music

Given $n$ integers $a_{1..n}$, find $n$ non-negative integers $b_{1..n}$ to maximize the value of $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$, where $\operatorname{f(x)}$ is the number of $1$ bits in the binary representation of $x$. The $n$ non-negative integers $b_{1..n}$ you find must satisfy $0\le b_1

The first line contains two integers $n, m$. The second line contains $n$ integers $a_1, a_2, ..., a_n$.

Output one integer in one line, which is the maximum value of $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$.

For $100\%$ of the testdata, $1\le n\le 200$, $n-1\le m\le 10^{18}$, and $|a_i|\le 10^{14}$. ---- ### Explanation Let $b_1=3, b_2=4, b_3=5$. Then the answer is $2\times 2+(-1)\times 1+3\times 2=9$. Translated by ChatGPT 5