# 「SFMOI Round I」Strange Dino Game

## 题目背景

[English statement](https://www.luogu.com.cn/problem/T517979). **You must submit your code at the Chinese version of the statement.**


![](https://cdn.luogu.com.cn/upload/image_hosting/59joca92.png?x-oss-process=image/resize,m_lfit,h_600)

![](https://cdn.luogu.com.cn/upload/image_hosting/iyhol5l6.png?x-oss-process=image/resize,m_lfit,h_600)

Watersphere 同学在家没网了，只好玩起了 dino 游戏，但是他很菜，一玩到后面就头晕眼花，所以想让你编个程序帮助他拿到更高分，于是有了这题。

本题的游戏背景是 [Dino](https://dinosaur.game)。可以考虑点击链接游玩，以便更好理解题意。

## 题目描述

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

- 玩家：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$ 时的一次跳跃。

![](https://cdn.luogu.com.cn/upload/image_hosting/1gxrno9x.png?x-oss-process=image/resize,m_lfit,h_400)

在一局游戏中，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 的最大得分。特别地，得分可以为无穷大。

可参阅样例解释的图片。

## 输入格式

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

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

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

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

## 输出格式

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

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

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
3
Dino!
```

## 样例 #2

### 样例输入 #2

```
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
```

### 样例输出 #2

```
6
```

## 样例 #3

### 样例输入 #3

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

### 样例输出 #3

```
16
```

## 样例 #4

### 样例输入 #4

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

### 样例输出 #4

```
22
```

## 提示

样例 $1$ 解释：  

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

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

![](https://cdn.luogu.com.cn/upload/image_hosting/ge17so5a.png?x-oss-process=image/resize,m_lfit,h_400)

### 数据范围

**本题采用捆绑测试。**

- 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$。

## 时空限制



时间限制
3.00s

内存限制
512.00MB

Tags: 模拟, 动态规划 DP, 贪心, 二分, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 省选/NOI−