CF2037F.Ardent Flames

你获得了新的限时活动角色 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$ 中，输出 Xilonen 至少击败 $k$ 个敌人所需的最少攻击次数。如果不存在某个 $p$ 能使至少 $k$ 个敌人最终被击败，则输出 $-1$。当敌人的生命值降至 $0$ 或以下时，视为被击败。

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

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

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

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

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

对于每个测试用例，输出一个整数，表示至少击败 $k$ 个敌人所需的最少攻击次数。如果不存在某个 $p$ 能使至少 $k$ 个敌人最终被击败，则输出 $-1$。

在第一个测试用例中，最优选择 $p=2$。每次攻击，第一个敌人受到 $5-|2-1|=4$ 点伤害，第二个敌人受到 $5$ 点伤害，第三个敌人受到 $4$ 点伤害，第四个敌人受到 $3$ 点伤害，第五个敌人受到 $2$ 点伤害。经过 $2$ 次攻击，前三个敌人会被击败。可以证明，无论选择哪个 $p$，都无法在少于 $2$ 次攻击内击败 $3$ 个敌人。

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

在第三个测试用例中，必须击败两个敌人。然而可以证明，无论选择哪个 $p$，都无法同时对两个敌人造成伤害，因此答案为 $-1$。

在第四个测试用例中，选择 $p=1$ 可以让我们在 $6969697$ 次攻击内击败第一个敌人。

在第五个测试用例中，选择 $p=10$ 可以让每个敌人每次受到 $1$ 点伤害。两名敌人都将在 $15$ 次攻击内被击败。

由 ChatGPT 4.1 翻译