[PA2019] Muzyka pop

题目描述

给定 $n$ 个整数 $a_{1..n}$，请找到 $n$ 个非负整数 $b_{1..n}$，使得 $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$ 的值最大，其中 $\operatorname{f(x)}$ 为 $x$ 在二进制下的 $1$ 的个数。

你找到的这 $n$ 个非负整数 $b_{1..n}$ 需要满足 $0\le b_1<b_2<...<b_n\le m$。

输入格式

第一行两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$。

输出格式

输出一行一个整数，即 $a_1\times \operatorname{f(b_1)}+a_2\times \operatorname{f(b_2)}+...+a_n\times \operatorname{f(b_n)}$ 的最大值。

样例 #1

样例输入 #1

3 5
2 -1 3

样例输出 #1

9

提示

对于 $100\%$ 的数据，$1\le n\le 200$，$n-1\le m\le 10^{18}$，$|a_i|\le 10^{14}$。

解释：

$b_1=3,b_2=4,b_3=5$，则答案为 $2\times 2+(-1)\times 1+3\times 2=9$。