题目描述

星际矿业公司在某星球发现了 $n$ 座矿石矿脉，每座矿脉初始蕴含 $a_i$ 单位的高纯度矿石量。每次对第 $i$ 座矿脉开采时，可获得一定的收益，收益与当前矿脉的矿石量相同。开采后该矿脉的矿石量会减少 $b_i$ 单位（当剩余量不足 $b_i$ 时，减少至 $0$，此后无法再开采矿石获得收益）。

由于星际开采能力有限，最多只能进行 $k$ 次开采操作（每次操作可选择此星球中任意一座矿脉进行开采）。为了最大化收益，公司需要制定最优的开采策略，确保在不超过 $k$ 次操作的前提下，获取的总收益尽可能多。

已知共有 $t$ 个星球的矿脉数据需要处理，每个星球的矿脉情况独立，请你计算在每个星球中采矿所能获取的最大收益。

输入格式

第一行输入一个整数 $t$（$1 \leq t \leq 1000$），表示星球的数量。

对于每个星球，输入格式如下：

第一行输入两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$，$1 \leq k \leq 10^9$），分别表示矿脉数量和最大开采次数。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每座矿脉的初始高纯度矿石量。

第三行输入 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^9$），表示每座矿脉每次开采后的减少量。

保证每个星球中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个星球，输出一行整数，表示在每个星球中采矿所能获取的最大收益。

5
3 4
5 6 7
2 3 4
5 9
32 52 68 64 14
18 14 53 24 8
5 1000
1 2 3 4 5
5 4 3 2 1
1 1000000
1000000
1
10 6
3 3 5 10 6 8 6 8 7 7
6 1 7 4 1 1 8 9 3 1

21
349
27
500000500000
47

提示

【样例解释】

对于此样例中的 $5$ 个星球中的第一个星球，三个矿脉采集的次数可以为 $(1, 1, 2)$ 或 $(1, 2, 1)$ 或 $(2, 1, 1)$，获得的最大收益为 $7 + 6 + 5 + 3 = 21$。

【数据范围】

对于所有数据，满足 $1 \leq t \leq 1000$，$1 \leq n \leq 10^5$，$1 \leq k \leq 10^9$，$1 \leq a_i, b_i \leq 10^9$，且每个星球中 $n$ 的总和不超过 $2 \times 10^5$。

::cute-table{tuack}

测试点	$t \leq$	$n \leq$	$k \leq$	$a_i, b_i \leq$
$1\sim 2$	$10^2$	$10^3$	$10^2$	$10^3$
$1\sim 5$	$200$	$10^4$	$50000$	$10^6$
$1\sim 10$	$10^3$	$10^5$	$10^9$