该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 $z$ 现在有 $n$ 个箱子，编号为$1 \sim n$，第 $i$ 个箱子中有 $a_i$ 个金币。小 $z$ 需要按照箱子编号从小到大依次打开所有箱子，一个箱子都需要一把钥匙。 现在有两种钥匙可以打开箱子:

1. A 钥匙，需要花费 $k$ 个金币；
2. B 钥匙，不需要花费任何金币，但是会将每个未打开的箱子中的金币减半，包括即将打开的箱子。例如:使用一把 B 钥匙即将打开第 $i$ 个箱子，那么第$i \sim n$个箱子的金币都会减半(例如:第$i \sim n$范围内的某个箱子原先金币数量为 $5$，减半之后变为 $2$)。

一把钥匙只能用于一个箱子，不能重复使用。

小 $z$ 一共需要使用 $n$ 把钥匙，每个钥匙打开一个箱子。初始时，小 $z$ 没有金币，也没有钥匙，如果想要使用一把A钥匙打开箱子，就需要购买它。允许小 $z$ 当前所拥有的金币数量为负数，例如：小 $z$ 有 $1$ 个金币，可以买一把价值为 $3$ 个金币的A钥匙，那么小 $z$ 当前拥有的金币数量是 $-2$。

请你帮助小 $z$ 计算，按照箱子编号从小到大依次打开所有箱子能获取的最大金币数量。

输入格式

第一行，包含两个整数$n$、$k$；

第二行，包含$n$个整数$a_1$、$a_2$、$\dots$、$a_n$。

输出格式

一行，包含一个整数，表示结果。

4 5
10 10 3 1

11

12 51
5 74 89 45 18 69 67 67 11 96 23 59

60

说明/提示

数据范围

• 对于 100% 的数据，$1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 10^9, 0 \leq a_i \leq 10^9$。