← 返回题目列表

Codeforces · 2037/F

F. 炽热的火焰

中文机器翻译题面 查看原题

您获得了新的限时活动角色希洛宁。你决定在战斗中使用她。

一条线上有 $$$n$$$ 个敌人。左边第 $$$i$$$ 敌人的生命值为 $$$h_i$$$,目前位于位置 $$$x_i$$$。 Xilonen 的攻击力为 $$$m$$$,你已经准备好和她一起打败敌人了。

希洛宁拥有强大的“踩地”攻击。在执行任何攻击之前,您选择一个整数 $$$p$$$ 并将 Xilonen 放置在那里($$$p$$$ 可以是任何整数位置,包括当前有敌人的位置)。之后,每次攻击,她对$$$p$$$位置的敌人造成$$$m$$$伤害(如果有的话),对$$$p-1$$$和$$$p+1$$$位置的敌人造成$$$m-2$$$伤害,对$$$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$$$, $$$x_i < x_{i+1}$$$ 对于所有 $$$1 \leq i < n$$$)

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

输出

对于每个测试用例,在新行中输出一个整数,即击败至少 $$$k$$$ 敌人所需执行的最小攻击次数。如果不可能找到 $$$p$$$ 使得最终至少 $$$k$$$ 敌人被击败,则输出 $$$-1$$$ 代替。

示例

输入 #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

输出 #1

2
2
-1
6969697
15
1000000000

注意

在第一个测试用例中,最佳选择 $$$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$$$ 攻击中被击败。