说明

时间限制：1 Sec 内存限制：256 MB 输入文件：upgrade.in 输出文件：upgrade.out

小明正在玩一款电脑游戏。为了升级他的角色，他得完成各种任务。游戏中有 $n$ 种任务，编号从 $1$ 到 $n$。

小明可以按如下规则完成任务：

• 第 $1$ 个任务始终可以完成；
• 必须把编号小于 $i$ 的任务都至少完成一次，才可以完成第 $i$ 个任务；

每次完成任务，角色都可以获得一定的经验值。一个任务是可以多次完成的：

• 首次完成第 $i$ 个任务，角色获得 $a_i$ 点经验值；
• 随后每次完成第 $i$ 个任务，角色获得 $b_i$ 点经验值。

小明的学习任务很繁重，他的闲暇时间仅够完成 $k$ 次任务。请你计算一下他最多可以获得多少点经验值。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 组询问，每组询问包含三行：

第一行为空格分隔的两个整数 $n$、$k$；

第二行为空格分隔的 $n$ 个整数 $a_1$、$a_2$、……、$a_n$；

第三行为空格分隔的 $n$ 个整数 $b_1$、$b_2$、……、$b_n$。

输出格式

$t$ 行，每行一个整数，第 $i$ 行为对第 $i$ 组询问的回答。

样例

样例 1

4
4 7
4 3 1 2
1 1 1 1
3 2
1 2 5
3 1 8
5 5
3 2 4 1 4
2 3 1 4 7
6 4
1 4 5 4 5 10
1 5 1 2 5 1

13
4
15
15

样例说明：

在第 $1$ 组询问中，一种完成任务的序列为：

序号	1	2	3	4	5	6	7
完成任务编号	1	2	3	4	2	4	4
获得经验值	4	3	1	2	1	1	1

可以证明 $4+3+1+2+1+1+1=13$ 是可以获得的最多的经验值。

在第 $2$ 组询问中，连续两次完成第 $1$ 个任务，可以获得经验值 $1+3=4$，很明显不能获得更多经验值了。

在第 $3$ 组询问中，一种完成任务的序列为：

序号	1	2	3	4	5
完成任务编号	1	2	2	2	3
获得经验值	3	2	3	3	4

可以证明 $3+2+3+3+4=15$ 是可以获得的最多的经验值。

数据范围

$1 \le t \le 10$

$1 \le n \le 2 \times 10^5$

$1 \le k \le 2 \times 10^5$

$1 \le a_i,b_i \le 10^3$

保证所有的询问中 $n$ 之和不超过 $2 \times 10^5$。