旅行推销员认为在陆地上安排行程是一个极其复杂的计算问题，因此他决定将业务转移到多瑙河的线性世界中。他有一艘非常快的船，可以让他瞬间从河上的任何地方到达任何地方，但不幸的是，这艘船的燃油消耗非常惊人。推销员每向上游（朝河流源头方向）行驶一米需要花费 $U$ 美元，每向下游（远离河流源头方向）行驶一米需要花费 $D$ 美元。

沿河有 $N$ 个贸易博览会，推销员想要参加。每个博览会仅举办一天。对于每个博览会 $X$，推销员知道其日期 $T_X$（以他购买船只后的天数计算）。他还知道博览会的位置 $L_X$（以从河流源头向下游计算的距离（米）为单位），以及如果他参加该博览会所能获得的利润 $M_X$（美元）。他必须从位于河边且距离河流源头 $S$ 米处的家中出发，并最终回到家中。

请帮助推销员选择参加哪些博览会（如果有的话）以及以什么顺序参加，以便他在旅程结束时获得最大利润。推销员的总利润定义为他参加博览会所获得的美元总额，减去他在河上上下往返所花费的美元总额。

请记住，如果博览会 $A$ 的举办日期早于博览会 $B$，则推销员只能按此顺序参加（即他不能先参加 $B$ 再参加 $A$）。但是，如果两个博览会在同一天举办，推销员可以按任意顺序参加这两个博览会。推销员一天内可以参加的博览会数量没有限制，但显然他不能参加同一个博览会两次并获得两次收益。他可以经过已经参加过的博览会而不获得任何收益。

任务

编写一个程序，根据所有博览会的日期、位置和盈利能力，以及推销员家的位置和他的旅行成本，确定他旅程结束时可能获得的最大利润。

数据范围

• $1 \le N \le 500,000$：博览会的数量
• $1 \le D \le U \le 10$：向上游 ($U$) 或下游 ($D$) 行驶一米的成本
• $1 \le S \le 500,001$：推销员家的位置
• $1 \le T_k \le 500,000$：博览会 $k$ 举办的日期
• $1 \le L_k \le 500,001$：博览会 $k$ 的位置
• $1 \le M_k \le 4,000$：参加博览会 $k$ 可获得的利润（美元）

输入格式

程序必须从标准输入读取以下数据： 第一行包含整数 $N, U, D$ 和 $S$，按此顺序排列，以空格分隔。 接下来的 $N$ 行描述了 $N$ 个博览会，顺序不限。这 $N$ 行中的第 $k$ 行描述了第 $k$ 个博览会，包含三个以空格分隔的整数：博览会的日期 $T_k$、其位置 $L_k$ 以及推销员的盈利能力 $M_k$。

注意：输入中给出的所有位置都是不同的。也就是说，没有两个博览会在同一位置举办，也没有博览会在推销员的家中举办。

输出格式

程序必须向标准输出写入一行，包含一个整数：推销员旅程结束时可能获得的最大利润。

子任务

• 对于总分 60 分的测试点，没有两个博览会在同一天举办。
• 对于总分 40 分的测试点，输入中的所有数字均不超过 5,000。
• 同时满足上述两个条件的测试点得 15 分。
• 至少满足上述两个条件之一的测试点得 85 分。

样例

样例输入 1

4 5 3 100
2 80 100
20 125 130
10 75 150
5 120 110

样例输出 1

50

说明

一个最优的行程是参加博览会 1 和 3（分别位于位置 80 和 75）。事件序列及其相关的利润和成本如下： 推销员向上游行驶 20 米，花费 100 美元。目前利润：-100 他参加博览会 1 并获得 100 美元。目前利润：0 他向上游行驶 5 米，花费 25 美元。目前利润：-25 他参加博览会 3 并获得 150 美元。目前利润：125 * 他向下游行驶 25 米返回家中，花费 75 美元。最终利润：50