Description

我们将问题放在二维平面上描述。我们给出一些游戏要素：

• 玩家：Dino。可以将其视为一个点。
• 障碍物：
  • 仙人掌：形如 $(x_i',0),(x_i',h_i)$ 的线段。
  • 飞鸟：形如 $(x_i,d_i),(x_i,u_i)$ 的线段。
• 游戏结束：Dino 与障碍物上的任意一点（包括线段端点）重合时，游戏结束。
• 起点：原点 $(0,0)$。
• 终点：使游戏结束的位置，位于第一象限（或 $x$ 轴上）。可能不存在（即游戏能无限进行）。
• 游戏分数：终点的 $x$ 坐标。终点不存在时定义为无穷大。
• 跳跃参数：正整数 $d,h$。
• 步行：Dino 在 $x$ 轴上沿着 $x$ 轴正方向移动。
• 跳跃：当 Dino 在 $x$ 轴上时，可以进行一次跳跃。以起跳点为原点，跳跃轨迹为$$f(x) = \begin{cases} \displaystyle \frac{h}{d}x & x\in [0, d) \\ \displaystyle-\frac{h}{d}x+2h & x\in [d, 2d) \\ \end{cases}$$
  • 需要注意的是，由上述定义可以推出：在一次跳跃后落地的瞬间进行第二次跳跃是合法的。
  • 需要注意的是，可以在任意实数点（只要在 $x$ 轴上）处开始跳跃。也就是说，跳跃不一定在整点开始。

下图展示了 $d=2,h=6$ 时的一次跳跃。

在一局游戏中，Dino 从起点出发向 $x$ 轴正方向移动。目标是最大化得分，即尽量避开障碍物，使自己移动的距离尽量长。

每一时刻，Dino 只能做一件事：步行，或跳跃。当且仅当 Dino 在 $x$ 轴上时可以进行跳跃。

形式化地说，Dino 的行为可以被描述为一个长度为 $(k+1)$ 的实数二元组序列 $[(x_0,t_0),(x_1,t_1),\cdots,(x_k,t_k)]$，满足：

• $x_0=0$；
• $t_i\in \{0,1\}$；
• $\forall 0\le i\lt k$, $x_i\lt x_{i+1}$；
• $t_i=1,i\lt k\implies x_{i+1}-x_i\ge 2d$；(二段跳是不允许的)
• $\forall 0\le i\lt k$, $t_i=t_{i+1}\implies t_i=t_{i+1}=1$。

当 $t_i=0$ 时，我们定义 Dino 在 $x_i$ 进入步行状态，否则定义 Dino 在 $x_i$ 进入跳跃状态。

当 Dino 与障碍物重合时，游戏结束。此时 Dino 在的位置为终点，得分为终点的 $x$ 坐标。

已知有 $b$ 只飞鸟和 $c$ 个仙人掌，求出 Dino 的最大得分。特别地，得分可以为无穷大。

可参阅样例解释的图片。

Input Format

本题单个测试点内有多组测试数据。

第一行，一个正整数 $T$，代表游戏次数。

接下来依次描述 $T$ 组数据：

• 每组数据第一行，两个正整数 $d,h$，表示 dino 的跳跃参数。
• 每组数据第二行，两个整数 $b,c$，表示飞鸟个数与仙人掌个数。
• 接下来 $b$ 行，每行三个正整数 $x_{i},u_i,d_i$，描述第 $i$ 只飞鸟。
• 接下来 $c$ 行，每行两个正整数 $x'_{i},h_{i}$，描述第 $i$ 株仙人掌。

Output Format

对于每组数据输出一行，表示得分的最大值。

特别地，如果得分为正无穷，输出 Dino!。

2
1 3
1 2
1 2 1
2 2
3 2
1000000000 1000000000
1 0
114514 1919 810

3
Dino!

1
8 16
8 3
5 18 13
4 20 10
6 13 1
2 17 11
1 11 6
5 1 1
2 6 3
1 16 1
7 20
7 13
3 2

6

1
5 5
1 2
5 5 1
6 1
16 3

16

1
5 5
1 4
19 10 8
4 1
15 1
22 2
20 1

22

Hint

样例 $1$ 解释：

• 对于第 $1$ 组数据，dino 无论如何也无法跳过连续的两株高为 $2$ 的仙人掌，答案即为第二株仙人掌的 $x$ 轴坐标。
• 对于第 $2$ 组数据，dino 可以在原点直接起跳跳过唯一的一只鸟，也完全可以不起跳从飞鸟下方走过。

其中第一组数据的解释如下所示，红线代表飞鸟，绿线代表仙人掌，粉线代表 Dino 的轨迹。

数据范围

本题采用捆绑测试。

• Subtask 1（5 pts）：$c=0$；
• Subtask 2（5 pts）：$b,c \le 10$；
• Subtask 3（20 pts）：$b=0$；
• Subtask 4（20 pts）：$1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i \le 10^5$;
• Subtask 5（40 pts）：无特殊限制。
• Subtask 6（10 pts）：无特殊限制。

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10$；
• $0 \le b,c \le 2\times 10^4$；
• $1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i\le 10^9$；
• $d_i\le u_i$。