F. 炽焰之焰
每次测试时间限制：4 秒
每次测试内存限制：256 兆字节

你获得了新的限时活动角色 Xilonen。你决定让她投入战斗。

战场上有 $n$ 个敌人排成一条直线。从左数第 $i$ 个敌人的生命值为 $h_i$，当前位于位置 $x_i$。
Xilonen 的攻击力为 $m$，你准备好用她击败敌人。

Xilonen 有一个强大的 “踩地”攻击。在开始任何攻击之前，你选择一个整数 $p$，将 Xilonen 置于该位置（$p$ 可以是任意整数位置，包括有敌人所在的位置）。
之后，每次攻击：

• 她对位置 $p$ 的敌人造成 $m$ 点伤害（如果该位置有敌人）；
• 对位置 $p-1$ 和 $p+1$ 的敌人造成 $m-1$ 点伤害；
• 对位置 $p-2$ 和 $p+2$ 的敌人造成 $m-2$ 点伤害；
• 以此类推。
  距离 Xilonen 至少 $m$ 远的敌人本次攻击不受伤害。

形式化地说：若敌人在位置 $x$，则每次攻击对其造成 $\max(0, m - |p - x|)$ 点伤害。
注意：你不能在不同的攻击中选择不同的 $p$。

在所有可能的 $p$ 中，输出为了击败 至少 $k$ 个敌人，Xilonen 必须发动的最小攻击次数。
如果不存在任何 $p$ 能最终击败至少 $k$ 个敌人，输出 $-1$。
敌人生命值 $\le 0$ 即视为被击败。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m, k$（$1 \le k \le n \le 10^5$，$1 \le m \le 10^9$）。

接下来一行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 10^9$）。

最后一行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$1 \le x_i \le 10^9$，$x_i < x_{i+1}$ 对所有 $1 \le i < n$ 成立）。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出

对每个测试用例，输出一行一个整数，表示击败至少 $k$ 个敌人所需的最少攻击次数。
如果不可能，输出 $-1$。

示例

输入

6
5 5 3
7 7 7 7 7
1 2 3 4 5
9 5 9
2 4 6 8 10 8 6 4 2
1 2 3 4 5 6 7 8 9
2 10 2
1 1
1 20
2 10 1
69696969 420420420
1 20
2 10 2
10 15
1 19
2 2 2
1000000000 1
1 3

输出

2
2
-1
6969697
15
1000000000

样例解释

• 第一个测试用例：最优选 $p=2$。每次攻击，敌人 $1$ 受到 $5 - |2-1| = 4$ 伤害，敌人 $2$ 受到 $5$ 伤害，敌人 $3$ 受到 $4$ 伤害，敌人 $4$ 受到 $3$ 伤害，敌人 $5$ 受到 $2$ 伤害。
  两次攻击后，前三个敌人被击败。可以证明，无论选哪个 $p$，都无法在少于 $2$ 次攻击内击败 $3$ 个敌人。

• 第二个测试用例：必须击败全部 $9$ 个敌人。选 $p=5$，所有敌人在 $2$ 次攻击内被击败。

• 第三个测试用例：必须击败两个敌人，但可以证明无论选哪个 $p$，都不能同时伤害到两个敌人，所以输出 $-1$。

• 第四个测试用例：选 $p=1$，可以在 $6969697$ 次攻击内击败第一个敌人。

• 第五个测试用例：选 $p=10$，每次攻击每个敌人受 $1$ 点伤害。两个敌人都在 $15$ 次攻击内被击败。