题目描述

强哥所在的学校正在举办“劳动之星”评选活动，每位同学都有一个初始劳动积分卡，上面的分数都是 1 分。同学们可以通过“学习进步”操作来提升自己的积分：

• 选择一位同学 $i$ 和一个正数 $x$，使该同学的积分变为：$$a_i = a_i + \frac{a_i}{x}$$ 其中 $a_i$ 是该同学当前的积分，$x > 0$。

学校为每位同学设定了一个目标积分 $b_i$。当某位同学的积分恰好等于目标积分 $b_i$ 时，他将获得对应的奖励积分 $c_i$。

活动规定总共最多进行 $k$ 次“学习进步”操作。问：在不超过 $k$ 次操作的情况下，同学们总共能获得的最大奖励积分数量是多少？

输入格式

第一行包含两个整数 $n, k$，分别表示学生人数和最多允许的操作次数。

第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示每位同学的目标积分。

第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，表示每位同学达成目标时可获得的奖励积分数量。

数据范围
$1 \le n \le 10^3$
$1 \le k \le 10^5$
$1 \le b_i \le 10^3$
$1 \le c_i \le 10^6$

输出格式

输出一个整数，表示在不超过 $k$ 次操作的前提下，能获得的最大奖励积分总数。

样例

输入：

5 9
5 2 5 6 3
5 9 1 9 7

输出：

30