[R71E]果肆连赠 - 代码源竞赛平台

时空限制

2S/512M

题目描述

有 $n$ 个水果排成一排，编号为 $1,2,\dots,n$。第 $i$ 个水果的初始价格为 $a_i$，当前价格记为 $a_i'$，初始时 $a_i'=a_i$。

在获得水果之前，你可以使用不超过 $k$ 张优惠券。每张优惠券可以选择一个当前价格大于 $0$ 的水果，将其当前价格变为

$$a_i' \mathrel{:=} \left\lfloor \frac{a_i'}{2} \right\rfloor.$$

其中，$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。同一个水果可以使用多张优惠券。

结束使用优惠券后，所有水果的当前价格固定。接下来，你可以通过以下方式获得水果：

1. 花费 $a_i'$ 购买一个尚未获得的水果 $i$；
2. 对于 $1\le i<n$，若已经获得水果 $i$，尚未获得水果 $i+1$，且 $a_i'\ge a_{i+1}'$，则可以免费获得水果 $i+1$。

“获得”包括购买和免费获得。求获得所有水果的最小总花费。

格式

输入格式

第一行包含两个整数 $n,k$，分别表示水果的数量和你初始拥有的优惠券数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 个水果的初始价格。

输出格式

输出一行一个整数，表示获得所有 $n$ 个水果所需支付的最小总费用。

样例

样例输入 #1

2 1
5 8

样例输出 #1

5

样例解释 #1

对水果 $2$ 使用一张优惠券后，其价格变为 $4$。花费 $5$ 购买水果 $1$，由于 $5\ge 4$，可以免费获得水果 $2$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$k\le$
$1$	$30$	$10$
$2$	$50$	$100$	$10^9$
$3$	$20$	$500$

对于 $100\%$ 的数据，满足 $1\le n\le 500$，$0\le k\le 10^9$，$0\le a_i\le 10^9$。