让它们相等

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有一个长度为 $n$、初始所有元素均为 $1$ 的数组 $a$，以及两个长度为 $n$ 的数组 $b,c$。

一次操作可以选择下标 $i$ 和正整数 $x$，把 $a_i$ 改为 $a_i+\left\lfloor\dfrac{a_i}{x}\right\rfloor$。你至多可以执行 $k$ 次操作。

操作结束后，每个满足 $a_i=b_i$ 的位置会贡献 $c_i$ 的收益。求最大总收益。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

每个测试用例的第一行包含两个整数 $n,k$。第二行包含 $n$ 个整数 $b_i$，第三行包含 $n$ 个整数 $c_i$。

输出格式

对每个测试用例输出一行一个整数，表示最大总收益。

样例输入 1

4
4 4
1 7 5 2
2 6 5 2
3 0
3 5 2
5 4 7
5 9
5 2 5 6 3
5 9 1 9 7
6 14
11 4 6 2 8 16
43 45 9 41 15 38

样例输出 1

9
0
30
167

数据范围

$1\le t\le100$，$1\le n\le1000$，$0\le k\le10^6$，$1\le b_i\le1000$， $1\le c_i\le10^6$；所有测试用例的 $n$ 之和不超过 $1000$。