P13649 [NOISG 2016] Panda Ski

冬奥会即将来临，Panda 先生一直在努力训练，准备参加滑雪项目。该项目在 Mt. Rar 山上举行，山高为 $H$。每个人都可以沿着中线滑道从山顶滑到山脚。为了增加难度，山上设置了 $N$ 个闸门，每个闸门都有一个得分，且位于不同高度，并分布在中线滑道的左侧或右侧。目标是从山顶滑到山脚，并通过经过某些闸门来获得分数。 第 $i$ 个闸门位于高度 $Y_i$，距离中线滑道右侧 $X_i$ 个单位。如果 $X_i$ 为负，则表示在中线滑道左侧。通过第 $i$ 个闸门可以获得 $S_i$ 分数，每个闸门只能首次通过时获得分数，重复通过不再计分。没有两个闸门在同一个点上。 Panda 先生希望最大化自己的得分。此外，Panda 先生知道自己滑雪技术一般，可能无法经过所有闸门。为了避免尴尬，他对每个闸门根据坡度、积雪量等因素给出了一个“易通过分数” $E_i$（分数越高越容易）。 具体来说，Panda 先生计算出：如果 $\max(|X_j - X_i|, Y_i - Y_j) \leq E_i$ 且 $Y_i \geq Y_j$，则可以从第 $i$ 个闸门滑到第 $j$ 个闸门。此外，可以从山顶到达任意一个闸门，也可以从任意一个闸门到达山脚。 Panda 先生被可能的滑行路径数量吓到了，他需要你的帮助，找出能获得最高分的滑行路径。

你的程序需要从标准输入读取数据。第一行包含两个正整数 $N$ 和 $H$。接下来的 $N$ 行，每行包含 4 个整数，分别为 $X_i, Y_i, S_i, E_i$，表示第 $i$ 个闸门的信息。

你的程序需要输出一行，一个整数，表示 Panda 先生能够获得的最大分数。

### 说明 只有 3 条可能的滑行路径： 1. 顶部 $\rightarrow (0, 5) \rightarrow$ 底部，得分：5 2. 顶部 $\rightarrow (3, 4) \rightarrow (1, 1) \rightarrow$ 底部，得分：$4 + 4 = 8$ 3. 顶部 $\rightarrow (-2, 3) \rightarrow (-1, 2) \rightarrow$ 底部，得分：$3 + 3 = 6$ 所以最高得分为 8。 ### 子任务 每个测试点的最大运行时间为 1.0 秒。你的程序将在以下输入范围下进行测试： | 子任务 | 分值 | $N$ | 其他限制 | | :-: | :-: | :-: | :-: | | 1 | 7 | $1 \leq N \leq 300$ | 所有 $E_i = 200000$ | | 2 | 8 | $1 \leq N \leq 300$ | 所有 $X_i = 0$，且 $E_i$ 相同 | | 3 | 11 | $1 \leq N \leq 300$ | $Y_i$ 互不相同 | | 4 | 13 | $1 \leq N \leq 2000$ | $Y_i$ 互不相同 | | 5 | 15 | $1 \leq N \leq 50000$ | $Y_i$ 互不相同，且 $E_i$ 相同 | | 6 | 13 | $1 \leq N \leq 50000$ | $E_i$ 相同 | | 7 | 16 | $1 \leq N \leq 50000$ | $Y_i$ 互不相同 | | 8 | 17 | $1 \leq N \leq 200000$ | $Y_i$ 互不相同 | 对于所有测试点，$-50000 \leq X_i \leq 50000$，$1 \leq Y_i \leq H \leq 200000$，$1 \leq S_i \leq 10^6$，$1 \leq E_i \leq 200000$。 由 ChatGPT 4.1 翻译