题目内容

一个串行执行的模型由 $n$ 个模块组成。第 $i$ 个模块的初始耗时为 $a_i$，并且存在一个不可突破的耗时下限 $b_i$，保证 $b_i \le a_i$。模型运行一次的总耗时等于所有模块当前耗时的累加。

你有 $m$ 天时间可以用于优化。每一天只能选择一个模块执行一次优化，同一个模块可以多次优化。若某个模块当前耗时为 $t$，一次优化会将它变为 $\lceil t/2 \rceil$，即 $t$ 的一半向上取整。只有在 $t > b_i$ 且 $\lceil t/2 \rceil \ge b_i$ 时，该模块才能被选择优化；因此，模块耗时永远不会低于 $b_i$，一旦达到 $b_i$ 就无法继续优化。如果没有任何模块可以继续优化，剩余天数不会改变总耗时。

请合理安排这 $m$ 天中的优化对象，使得 $m$ 天后所有模块的耗时总和最小，并求出这个最小值。

约束条件

模块数量 $n$ 的范围是从 $1$ 到 $10^3$。

优化天数 $m$ 的范围是从 $0$ 到 $10^3$。

对于每个模块，$b_i$ 和 $a_i$ 都是整数，满足 $b_i \le a_i$，并且都位于 $1$ 到 $10^5$ 之间。

输入描述

输入共三行。

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

第二行依次给出 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个模块的初始耗时。

第三行依次给出 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示每个模块的耗时下限。

输出描述

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

样例1

输入

3 2
10 20 30
1 1 1

输出

35

说明

初始总耗时为 $10+20+30=60$。三个模块当前一次优化可减少的量分别为：模块 1 为 $10-\lceil 10/2 \rceil=5$，模块 2 为 $20-\lceil 20/2 \rceil=10$，模块 3 为 $30-\lceil 30/2 \rceil=15$。

第 1 天选择减少量最大的模块 3，其耗时从 30 变为 15，总和变为 45。此时模块 3 下一次优化可减少 $15-\lceil 15/2 \rceil=7$。

第 2 天选择减少量最大的模块 2，其耗时从 20 变为 10，最终总和为 $10+10+15=35$。

样例2

输入

2 5
1 2
1 1

输出

2

说明

初始总耗时为 $1+2=3$。模块 1 当前耗时已经是下限 1，无法继续优化。模块 2 当前耗时为 2，优化后为 $\lceil 2/2 \rceil=1$，不低于下限 1，可以减少 1。

第 1 天选择模块 2 后，两个模块的耗时都变为 1，总耗时为 2。之后没有模块能继续优化，剩余 4 天不会改变结果，因此输出 2。

样例3

输入

1 3
100
1

输出

13

说明

初始只有一个模块，耗时为 100，下限为 1。

第 1 天优化后耗时变为 $\lceil 100/2 \rceil=50$。第 2 天优化后变为 $\lceil 50/2 \rceil=25$。第 3 天优化后变为 $\lceil 25/2 \rceil=13$。

三次优化均满足不低于下限 1 的条件，最终总耗时为 13，因此输出 13。