← 返回题目列表

Codeforces · 1840/F

F. 轨道炮

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

Tema 正在玩一个非常有趣的电脑游戏。

在下一次任务中,特马的角色发现自己身处一个陌生的星球。与地球不同,这颗行星是平坦的,可以表示为 $$$n \times m$$$ 矩形。

Tema 的角色位于坐标为 $$$(0, 0)$$$ 的点。为了成功完成任务,他需要活着到达坐标$$$(n, m)$$$的地点。

令电脑游戏的角色位于坐标$$$(i,j)$$$处。从第一秒开始,Tema 可以:

- 要么使用垂直超级跳跃技术,之后他的角色将在第二秒结束时到达坐标$$$(i + 1, j)$$$;
- 或使用水平超级跳跃技术,之后他的角色将在第二秒结束时到达坐标$$$(i, j + 1)$$$;
- 或者特马可以选择不进行超级跳跃,在这种情况下他的角色在这一秒内不会移动;

居住在这个星球上的外星人非常危险且充满敌意。因此,他们会用轨道炮射击 $$$r$$$ 次。

每次射击垂直或水平完全穿透一个坐标。如果角色在射击时(在第二秒结束时)位于其撞击线上,他就会死亡。

由于 Tema 查看了游戏的源代码,他知道每次射击的完整信息 - 时间、穿透坐标和射击方向。

角色到达所需点的最短时间是多少?如果他注定要死并且无法到达坐标$$$(n, m)$$$的点,则输出$$$-1$$$。

输入

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

然后按照测试用例的描述进行操作。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \cdot m \le 10^4$$$) - 行星的大小、高度和宽度。

每个测试用例的第二行包含一个整数 $$$r$$$ ($$$1 \le r \le 100$$$) — 射击次数。

然后按照 $$$r$$$ 行,每行描述一个镜头。

镜头由三个整数 $$$t$$$、$$$d$$$、$$$coord$$$ 描述。其中 $$$t$$$ 是射击的第二个时间 ($$$1 \le t \le 10^9$$$)。 $$$d$$$ 是射击方向($$$d = 1$$$ 表示水平射击,$$$d = 2$$$ 表示垂直射击)。 $$$coord$$$ 是穿透坐标的大小($$$0 \le coord \le n$$$ for $$$d = 1$$$,$$$0 \le coord \le m$$$ for $$$d = 2$$$)。

所有测试用例的乘积 $$$n \cdot m$$$ 之和不超过 $$$10^4$$$。

输出

对于每个测试用例,输出一个数字 - 角色到达坐标 $$$(n, m)$$$ 的最短时间,如果他注定要死,则输出 $$$-1$$$。

示例

输入 #1

5
1 3
4
1 2 0
2 2 1
3 2 2
4 1 1
3 3
6
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
2 1
3
7 1 2
2 1 1
7 2 1
2 2
5
9 1 2
3 2 0
5 1 2
4 2 2
7 1 0
4 6
7
6 1 2
12 1 3
4 1 0
17 2 3
1 2 6
16 2 6
3 2 4

输出 #1

5
-1
3
6
10

注意

在第一个测试用例中,角色可以按如下方式移动:$$$(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$$$。

在第二个测试用例中,角色将无法离开在第二个 $$$2$$$ 处被射击完全穿透的矩形。