题目描述
小明现在有n个箱子，编号为1~n，第i个箱子中有ai个金币。小明需要按照箱子编号从小到大依次打开所有箱子，一个箱子都需要一把钥匙，现在有两种钥匙可以打开箱子:
- A钥匙，需要花费k个金币；
- B钥匙，不需要花费任何金币，但是会将每个未打开的箱子中的金币减半，包括即将打开的箱子。例如:使用一把B钥匙即将打开第i个箱子，那么第i~n个箱子的金币都会减半(例如:第i~n范围内的某个箱子原先金币数量为5，减半之后变为2)。
一把钥匙只能用于一个箱子，不能重复使用。
小明一共需要使用n把钥匙，每个钥匙打开一个箱子。初始时，小明没有金币，也没有钥匙，如果想要使用一把A钥匙打开箱子，就需要购买它。允许小明当前所拥有的金币数量为负数，例如：小明有1个金币，可以买一把价值为3个金币的A钥匙，那么小明当前拥有的金币数量是-2。
请你帮助小明计算，按照箱子编号从小到大依次打开所有箱子能获取的最大金币数量。
