P5902 [IOI 2009] Salesman

IOI2009 D2T4

旅行商已经发现，最佳的陆上旅行计划是一个难以解决的计算问题，所以他将他的生意转移到多瑙河的线性世界。他有一条很快的船，可以在很短的时间内把他从沿河的任何地方送到任何地方，但不幸的是，这条船耗油量很大。旅行商向上游（靠近河流源头的方向）移动每一米的成本为 $U$ 美元，向下游（远离河流源头的方向）移动每一米的成本为 $D$ 美元。 沿河有 $N$ 个展销会，旅行商想参加。每场展销会只举行一天。对于每个展销会 $X$，旅行商知道它的日期 $T_X$（他买船后的天数为第 $0$ 天），集市的位置 $L_X$ 和他在这场集市上能获得的盈利 $M_X$。位置表示集市到河流源头的距离，以米为单位。他必须在位置为 $S$ 的家 **开始和结束** 他的旅程。 帮助旅行商选择参加哪些展销会（如果有的话）以及按什么顺序，这样他可以在旅行结束时最大化他的利润。旅行商的总利润是指他在参加集市时获得的美元减去他在河上下游旅行所花费的美元的总和。 请记住，如果展销会 $A$ 的举办时间早于展销会 $B$，则旅行商只能按此顺序去展销会（即，他不能先去展销会 $B$，然后再去展销会 $A$）。但是，如果两个集市在同一天举行，旅行商可以按任何顺序参观。旅行商一天去多少个集市是没有限制的，但他不能在同一个集市盈利两次。他可以经过他已经参观过的集市而一无所获。 **任务**：编写一个程序，给定所有展销会的日期，位置和旅行商的盈利额，以及旅行商的家的位置和他移动的代价，求出他在旅行结束时的最大利润。

无

无

### 样例解释 在一个最优方案中，旅行商参加了编号为 $1$ 和 $3$ 的展销会（位置分别为 $80$ 和 $75$）。事件序列以及对应的利润如下： - 旅行商从家出发，向上游移动 $20$ 米，花费 $100$ 美元。目前利润：$-100$。 - 旅行商参加展销会 $1$ 并赚取 $100$ 美元。目前利润：$0$。 - 旅行商向上游移动 $5$ 米，花费 $25$ 美元。目前利润 $-25$。 - 旅行商参加展销会 $3$ 并赚取 $150$ 美元。目前利润：$125$。 - 旅行商向下游移动 $25$ 米，回到自己的家，花费 $75$ 美元。最终利润：$50$。 ### 数据范围与约定 - 对于 $60\%$ 的数据，没有两个展销会在同一天举行。 - 对于 $40\%$ 的数据，输入的所有数不超过 $5000$。 - 同时满足上述两个条件的数据有 $15\%$，至少满足上述一个条件的数据有 $85\%$。 - 对于 $100\%$ 的数据，$1 \le N, T_k \le 5\times 10^5$，$1 \le D \le U \le 10$，$1 \le S, L_k \le 5 \times 10^5 +1$，$1 \le M_k \le 4000$。