题目描述

有 $n$ 种不同的卡牌，其中第 $i$ 种卡牌的基础价值为 $v_i$，数量为 $a_i$ 张。

你需要从这些卡牌中恰好选出 $X$ 张，组成自己的卡组。

对于同一种卡牌，随着你选取的数量增加，它后续的价值会下降。具体地，若某种基础价值为 $v$ 的卡牌已经被选了 $k$ 张，那么下一张这种卡牌的价值为：

$\lfloor x \rfloor$ 表示对 $x$ 向下取整，即不超过 $x$ 的最大整数。

也就是说：

• 选第 $1$ 张该种卡牌时，价值为 $\left\lfloor \frac{v}{1} \right\rfloor = v$；
• 选第 $2$ 张时，价值为 $\left\lfloor \frac{v}{2} \right\rfloor$；
• 选第 $3$ 张时，价值为 $\left\lfloor \frac{v}{3} \right\rfloor$；
• 依此类推。

每种卡牌至多只能选取 $a_i$ 张。

现在，请你计算：恰好选出 $X$ 张卡牌时，能够得到的最大总价值是多少。

输入格式

输入共三行。

第一行包含两个整数 $n, X$，分别表示卡牌种类数和需要选取的卡牌总数。

第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$，表示每种卡牌的基础价值。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每种卡牌可供选取的数量。

输出格式

输出一行一个整数，表示最大总价值。

6 6
1 1 2 3 4 5
1 2 1 2 3 4

18

提示

【样例说明】

将所有可能选取的单张卡牌价值展开后，可得：

• 第 $1$ 种卡牌可贡献：$1$
• 第 $2$ 种卡牌可贡献：$1, 0$
• 第 $3$ 种卡牌可贡献：$2$
• 第 $4$ 种卡牌可贡献：$3, 1$
• 第 $5$ 种卡牌可贡献：$4, 2, 1$
• 第 $6$ 种卡牌可贡献：$5, 2, 1, 1$

从中选出最大的 $6$ 个值：$5, 4, 3, 2, 2, 2$，它们的和为：$5+4+3+2+2+2 = 18$，因此答案为 $18$。

【评测用例规模与约定】

对于 $50\%$ 的评测用例，$1 \le n, X \le 5000$；

对于所有的评测用例，满足：$1 \le n \le 2 \times 10^5$，$0 \le X, a_i \le 2 \times 10^5$，$0 \le v_i \le 10^9$。

保证所有卡牌总数不少于 $X$。