有 $n$ 名足球运动员，编号为 $1, 2, \dots, n$，排列在一条直线上。第 $i$ 名运动员位于位置 $x_i$。最初，1 号运动员持有足球。运动员不允许移动，但他们可以互相传球。他们知道彼此的位置。他们的目标是让球以最短的时间到达 $n$ 号运动员手中。不同的运动员有不同的踢球速度。形式化地说，第 $i$ 名运动员踢球的速度为 $1/s_i$。

换句话说，从运动员 $i$ 直接传球给运动员 $j$ 所需的时间为 $s_i \cdot |x_i - x_j|$。他们改变球的方向次数不得超过 $k$ 次。如果连续两次传球 $a \to b$ 和 $b \to c$ 满足 $a$ 和 $c$ 位于 $b$ 的同一侧（即都在 $b$ 的左侧或都在 $b$ 的右侧），则称球的方向发生了改变。注意，第一次传球不计入方向改变次数。

球到达 $n$ 号运动员所需的最短时间是多少？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例的描述。

每个测试用例的第一行包含 $n$ 和 $k$，分别表示运动员的人数和允许改变球方向的最大次数。

第二行包含 $n$ 个空格分隔的整数 $x_1, x_2, \dots, x_n$，表示运动员的位置。

第三行包含 $n$ 个空格分隔的整数 $s_1, s_2, \dots, s_n$，其中 $s_i$ 表示运动员 $i$ 踢球速度的倒数。

• $1 \le T \le 10^5$
• $1 \le n \le 3 \times 10^5$
• $0 \le k \le n$
• 所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$
• 对于所有 $1 \le i \le n$，有 $1 \le x_i, s_i \le 10^9$
• 对于 $i \neq j$，有 $x_i \neq x_j$

输出格式

对于每个测试用例，输出一行，表示球到达 $n$ 号运动员所需的最短时间。

样例

输入 1

2
4 2
3 2 1 6
3 1 1 3
2 0
1 2
1 2

输出 1

7
1

说明

在第一个测试用例中，最优方案是将球从 1 号球员传给 2 号球员，然后再从 2 号球员传给 4 号球员。注意，球的方向恰好改变了一次。所用时间为 $3 \cdot (3 - 2) + 1 \cdot (6 - 2) = 7$。

在第二个测试用例中，只有一种方案，即直接将球从 1 号球员传给 2 号球员。