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

Mateusz 刚刚创作了一段新旋律，并打算为它匹配合适的节拍。旋律持续 $n$ 秒，其中某些时刻可能比其他时刻更好。第 $i$ 秒旋律的质量由整数 $a_i$（可能是负数）描述，需要为其选择一个非负整数位增强系数 $b_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)$$

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

Mateusz 的目标是选择合适的位增强系数，以最大化歌曲的最终质量。他能得到的最大值是多少？

输入格式

输入的第一行包含两个整数 $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$$