解题思路

题目中一次优化只会影响一个模块，并且总耗时等于所有模块耗时之和，所以可以把问题看成：

• 初始总和为 $\sum a_i$
• 每次操作选择一个模块，让总和尽量减少
• 做 $m$ 次后，总和最小

对于某个模块，若当前耗时为 $t$，下限为 $b_i$，那么一次优化后变成：

题目内容

现在有一个模型，它由 $n$ 个模块组成，每个模块有不同的耗时，各个模块串行执行，模型的总耗时等于各模块耗时的累加。为了提升模型性能，我们需要对模块进行优化。每次优化可以将模块耗时减半（向上取整），但每个模块都有其耗时下限，优化后的耗时不会低于该下限。

给定 $n$ 个模块，每个模块的初始耗时为 $a_i$​，其耗时下限为 $b_i$​（保证 $b_i​≤a_i$​）。

现有 $m$ 天时间，每天可以选择一个模块进行一次优化（同一模块可以优化多次）。

请合理安排优化策略，使得 $m$ 天后所有模块的总耗时最小。

优化规则

• 如果一个模块当前耗时为 $t$，优化一次后耗时变为 $ceil(t/2)$（向上取整）。

• 优化后的耗时不能低于该模块的下限 $b_i$​。

• 如果模块当前耗时已经等于下限 $b_i$​，则无法继续优化该模块。

约束条件

$1≤n≤10^3$

$0≤m≤10^3$

$1≤b_i​≤a_i​≤10^5$

输入描述

第一行：两个整数 $n,m$，分别表示模块数量和优化天数

第二行：$n$ 个整数，表示每个模块的初始耗时 $a_1​,a_2​,…,a_n$

第三行：$n$ 个整数，表示每个模块的耗时下限 $b_1​,b_2​,…,b_n$​

输出描述

输出一个整数，表示 $m$ 天后所有模块的最小总耗时

样例1

输入

2 0
50 100
10 10

输出

150

说明

$m=0$，没有优化，总体耗时为 $50+100=150$。

样例2

输入

2 3
100 80
40 10

输出

70

说明

第一天优化模块 $1$，时间从 $100$ 减少到 $50$；

第二天优化模块 $1$，时间从 $80$ 减少到 $40$；

第三天优化模块 $2$，时间从 $40$ 减少到 $20$；

最终总耗时 $30+40=70$。

样例3

输入

2 10
6 8
3 4

输出

7

说明

两个模块各进行一次优化后（需要 $2$ 天），均达到耗时下限，此后 $8$ 天无法继续优化。

所以最终所有模块的最小总耗时为 $3+4=7$。