← 返回题目列表

Codeforces · 1626/C

C. 怪物和法术

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

Monocarp 又在玩电脑游戏了。他是一名巫师学徒,只懂得一种咒语。幸运的是,这个法术可以对怪物造成伤害。

他当前所在的关卡包含 $$$n$$$ 怪物。其中第 $$$i$$$ 出现在关卡开始后 $$$k_i$$$ 秒,并拥有 $$$h_i$$$ 生命值。作为附加约束,$$$h_i \le k_i$$$ 对于所有 $$$1 \le i \le n$$$。所有 $$$k_i$$$ 都是不同的。

Monocarp 可以在关卡开始后的正整数秒内施放该法术:$$$1, 2, 3, \dots$$$ 该法术的伤害计算如下。如果他在前一秒没有施展该法术,则伤害为$$$1$$$。否则,令前一秒的伤害为$$$x$$$。然后他可以选择伤害为 $$$x + 1$$$ 或 $$$1$$$。法术需要消耗法力:施展伤害为 $$$x$$$ 的法术会消耗 $$$x$$$ 法力。法力不会再生。

要杀死第 $$$i$$$ 个怪物,Monocarp 必须在怪物出现的那一刻施放伤害至少为 $$$h_i$$$ 的法术,即 $$$k_i$$$。

请注意,即使当前秒没有怪物,Monocarp 也可以施展该法术。

施展法术所需的法力值是所有施展法术的法力用量之和。计算 Monocarp 杀死所有怪物所需的最少法力值。

可以证明,在问题的约束下,总是有可能杀死所有怪物。

输入

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

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 关卡中怪物的数量。

测试用例的第二行包含 $$$n$$$ 整数 $$$k_1 < k_2 < \dots < k_n$$$ ($$$1 \le k_i \le 10^9$$$) — 从第 $$$i$$$ 个怪物出现开始的秒数。所有 $$$k_i$$$ 都不同,$$$k_i$$$ 按升序提供。

测试用例的第三行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le k_i \le 10^9$$$) — 第 $$$i$$$ 个怪物的生命值。

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

输出

对于每个测试用例,打印一个整数 - Monocarp 杀死所有怪物所需的最少法力值。

示例

输入 #1

3
1
6
4
2
4 5
2 2
3
5 7 9
2 1 2

输出 #1

10
6
7

注意

在示例的第一个测试用例中,Monocarp 从一开始就可以施放法术 $$$3, 4, 5$$$ 和 $$$6$$$ 秒,分别造成 $$$1, 2, 3$$$ 和 $$$4$$$ 伤害。 $$$6$$$秒造成的伤害为$$$4$$$,这确实大于或等于出现的怪物的生命值。

在示例的第二个测试用例中,Monocarp 从一开始就可以施放法术 $$$3、4$$$ 和 $$$5$$$ 秒,分别造成 $$$1、2$$$ 和 $$$3$$$ 伤害。

在示例的第三个测试用例中,Monocarp 从一开始就可以施放法术 $$$4, 5, 7, 8$$$ 和 $$$9$$$ 秒,造成伤害分别为 $$$1, 2, 1, 1$$$ 和 $$$2$$$。