Description

冬奥会即将来临，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 先生被可能的滑行路径数量吓到了，他需要你的帮助，找出能获得最高分的滑行路径。

Input Format

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

Output Format

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

5 5
0 5 5 1
3 4 4 3
-2 3 3 2
1 1 4 4
-1 2 3 1

8

Hint

说明

只有 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 秒。你的程序将在以下输入范围下进行测试：

对于所有测试点，$-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 翻译