题目描述

给定长度为 $n$ 的 $a,b$ 数组，$a$ 数组的所有元素都等于 $1$，同时可以执行以下操作：

• 选择两个整数 $i,x$，$i$ 为 $a$ 数组的下标，使得 $a_i=a_i+\frac{a_i}{x}$，$(1≤i≤n,x>0)$。

当操作后，所有 $a_i==b_i$的下标，你将获得 $c_i$ 乔斯币。

问执行不超过 $k$ 次操作的情况下，可以获得的最大乔斯币数量？

输入格式

第一行包含两个整数 $n,k$，表示数组的大小和最大操作次数。

第二行包含 $n$ 个整数，$b_1,b_2,b_3,...,b_n$。

第三行包含 $n$ 个整数，$c_1,c_2,c_3,...,c_n$。

$(1≤n≤10^3,1≤k≤10^5)$

$(1≤b_i≤10^3,1≤c_i≤10^6)$

输出格式

输出一行一个整数，表示不超过 $k$ 次操作可以获得的最大乔斯币数量。

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

30

提示