You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

有一个大小为 $n$ 的数组 $a$ ，一开始 $a$ 的所有元素都为 $1$ ，你可以进行以下操作：

• 选择两个整数 $i$ $(1 \leq i \leq n)$, $x$ $(x>0)$，让 $a_i=a_i+ \lfloor \frac{a_i}{x} \rfloor$ 你可以进行最多 $k$ 次操作，操作结束后，对于那些满足 $a_i = b_i$ 的位置，你会收到 $c_i$ 的收益 $(1 \leq i \leq n)$ 你的任务是在 $k$ 次操作内最大化收益。

Input Format

第一行包括两个整数 $n$, $k$ $(1 \leq n \leq 10^3;0 \leq k \leq 10^6)$ ，代表数组的大小和最大操作次数。 第二行包括 $n$ 个整数 $b_1,b_2,...,b_n$ $(1 \leq b_i \leq 10^3)$ 。 第三行包括 $n$ 个整数 $c_1,c_2,...,c_n$ $(1 \leq c_i \leq 10^6)$ 。

Output Format

输出一个整数，代表 $k$ 次操作内的最大收益。

Sample

Input1:

4 4
1 7 5 2
2 6 5 2

Output1:

9

Input2:

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

Output2:

30