Radewoosh 热爱流行音乐。它令人放松，适合跳舞，甚至对编程也有帮助。然而，所有这些优点都需要旋律与节拍的完美契合。

Radewoosh 刚刚创作了一段新旋律，并打算为它匹配一些好的节拍。这段旋律持续 $n$ 秒，其中某些时刻的效果比其他时刻好得多。旋律第 $i$ 秒的质量由整数 $a_i$（可能为负）描述。他需要选择非负整数 $b_i$ 作为节拍增益系数。该系数会将第 $i$ 秒的质量放大 $C(b_i)$ 倍，其中 $C(b_i)$ 是 $b_i$ 二进制表示中 $1$ 的个数。例如，选择 $b_i = 13$ 会使第 $i$ 秒的旋律获得三倍增益，因为 $13$ 的二进制表示为 $1101$，其中包含三个 $1$。

整首歌曲的最终质量可以描述为： $$a_1 \cdot C(b_1) + a_2 \cdot C(b_2) + \dots + a_n \cdot C(b_n)$$

每个人都喜欢节拍增益递增的歌曲，Radewoosh 也不例外。节拍增益系数必须构成一个非负整数的递增序列，且受到上限 $m$ 的限制： $$0 \le b_1 < b_2 < \dots < b_n \le m$$

Radewoosh 的目标是选择节拍增益系数，以最大化歌曲的最终质量。 他能得到的最大值是多少？

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 200, n - 1 \le m \le 10^{18}$)，分别表示歌曲的长度（秒）和节拍增益系数的上限。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($-10^{14} \le a_i \le 10^{14}$)，表示旋律对应秒数的质量。

输出格式

输出一个整数，即歌曲最终质量的最大可能值。

样例

样例输入 1

3 5
2 -1 3

样例输出 1

9

样例输入 2

3 2
1 1 -1

样例输出 2

0

说明

第一个样例的解释：旋律由三秒组成，质量分别为 $2, -1, 3$。注意，秒的质量可能是负数！最优的序列 $b$ 为 $b_1 = 3, b_2 = 4, b_3 = 5$。此时我们得到歌曲的质量为： $$a_1 \cdot C(b_1) + a_2 \cdot C(b_2) + a_3 \cdot C(b_3) = 2 \cdot C(3) + (-1) \cdot C(4) + 3 \cdot C(5) = 2 \cdot 2 + (-1) \cdot 1 + 3 \cdot 2 = 9$$