减半之谜 题目描述 小明现在有n个箱子，编号为1~n，第i个箱子中有ai个金币。小明需要按照箱子编号从小到大依次打开所有箱子，一个箱子都需要一把钥匙，现在有两种钥匙可以打开箱子: A钥匙，需要花费k

减半之谜15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
题目描述15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
小明现在有n个箱子，编号为1~n，第i个箱子中有ai个金币。小明需要按照箱子编号从小到大依次打开所有箱子，一个箱子都需要一把钥匙，现在有两种钥匙可以打开箱子:15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
A钥匙，需要花费k个金币；15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
B钥匙，不需要花费任何金币，但是会将每个未打开的箱子中的金币减半，包括即将打开的箱子。例如:使用一把B钥匙即将打开第i个箱子，那么第i~n个箱子的金币都会减半(例如:第i~n范围内的某个箱子原先金币数量为5，减半之后变为2)。15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一把钥匙只能用于一个箱子，不能重复使用。15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
小明一共需要使用n把钥匙，每个钥匙打开一个箱子。初始时，小明没有金币，也没有钥匙，如果想要使用一把A钥匙打开箱子，就需要购买它。允许小明当前所拥有的金币数量为负数，例如：小明有1个金币，可以买一把价值为3个金币的A钥匙，那么小明当前拥有的金币数量是-2。15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
请你帮助小明计算，按照箱子编号从小到大依次打开所有箱子能获取的最大金币数量。15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行，包含两个整数n、k; 第二行，包含n个整数a1、a2、...、an。15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一行，包含一个整数，表示结果。15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
数据范围15E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1≤n≤2*10^5,0≤k≤10^9，0≤ai≤10^915E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入样例115E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4 5 10 10 3 115E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出样例115E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1115E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入样例215E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
12 51 5 74 89 45 18 69 67 67 11 96 23 5915E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出样例215E100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
60