#P18538. Passing Game

Passing Game

Passing Game

有 nn 名足球运动员位于一条直线上,编号为 1,2,…,n1,2,\ldots,n。第 ii 名运动员的位置是 xix_i。最初,球在第 11 名运动员手中。

运动员不能移动,但可以互相传球,并且知道彼此的位置。他们希望让球在尽可能短的时间内到达第 nn 名运动员。

不同运动员的踢球速度不同:第 ii 名运动员踢出的球速度为 1/si1/s_i。因此从运动员 ii 直接传给运动员 jj,耗时为

si∣xi−xj∣.s_i\lvert x_i-x_j\rvert.

球的运动方向至多可以改变 kk 次。如果连续两次直接传球为 a→ba\to b 和 b→cb\to c,并且 a,ca,c 位于 bb 的同一侧(都在左边或都在右边),就算发生一次方向改变。第一次传球不算改变方向。

请计算让球到达第 nn 名运动员所需的最短时间。

输入格式

第一行一个整数 TT,表示测试用例数。随后依次给出 TT 个测试用例,每例三行:

  • 第一行两个整数 n,kn,k,分别表示运动员人数和允许改变方向的最大次数;
  • 第二行 nn 个整数 x1,x2,…,xnx_1,x_2,\ldots,x_n,表示位置;
  • 第三行 nn 个整数 s1,s2,…,sns_1,s_2,\ldots,s_n,表示踢球速度的倒数。

限制:

  • 1≤T≤1051\le T\le10^5;
  • 1≤n≤3×1051\le n\le3\times10^5;
  • 0≤k≤n0\le k\le n;
  • 同一输入文件中,所有测试用例的 nn 之和不超过 3×1053\times10^5;
  • 对每个 ii,1≤xi,si≤1091\le x_i,s_i\le10^9;
  • 对任意 i≠ji\ne j,xi≠xjx_i\ne x_j。

输入中的运动员编号不保证按坐标排列。

输出格式

每个测试用例输出一行,一个整数,表示最短时间。n=1n=1 时球已在目标运动员手中,所需时间为 00。

原样例

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