题目描述

旅行商认定如何优化旅行路线是一个非常棘手的计算问题，所以他决定沿着线性的多瑙河开展他的业务。他有一条快船能够在瞬间沿着多瑙河把他从任意开始的位置带到任意目的地，但是这条船很费油。它逆流而上（驶向源头的方向）每米花费 $U$ 元，顺流而下每米花费 $D$ 元（驶离源头的方向）。

沿着多瑙河有 $N$ 个展销会是旅行商所感兴趣的。每个展销会只持续一天。对于任意一个展销会 $X$，旅行商知道以下几条信息：

1. 展销日期是 $T_x$（该日期是从旅行商买船之日算起过去的天数）；
2. 展销地点是 $L_x$ （该地点用它与源头的距离表示，单位为米）；
3. 参加该展销会能赚到的钱数是 $M_x$元。

旅行商开始和结束旅程的地点都是他位于多瑙河边的家 $S$ （用它与源头的距离表示，单位为米）。

请帮助旅行商选择他是否参加，如果参加应该以什么样的顺序参加哪些展销会才能在旅行结束时获得最多的总收益。旅行商的总收益定义为他参加的所有展销会的收益和，减去他在河上顺流和逆流航行的总花费。

注意：如果展销会 $A$ 在展销会 $B$ 之前举行并且旅行商要参加这两个展销会，旅行商必须先参加 $A$ ，之后才能参加 $B$（即他不能先参加 $B$ 后参加 $A$）。当两个展销会在同一天举行，他可以按任意顺序参加这两个展销会。旅行商在一天之内参加的展销会的数目没有限制，但是他不能参加同一个展销会两次并在一个展销会上获得两次收益。他可以经过他已经参加过的展销会而不再获得任何收益。

输入格式

第一行依次包含整数 $N, U, D, S$ ，整数之间用空格隔开。

接下来的 $N$ 行描述了 $N$ 个展销会的情况（不按特定顺序排列）。

这 $N$ 行中的第 $k$ 行描述了第 $k$ 个展销会的情况，它包含三个整数分别表示展销会的日期 $T_k$，地点 $L_k$，和收益 $M_k$。

注意：输人中给出的所有地点都是不同的。即没有两个展销会在同一个地点举行，也没有展销会在旅行商的家的位置上举行。

输出格式

输出旅行商结束旅行时能够获得的最大总收益。

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

50

数据范围与约定

对于 $100\%$ 的数据，$1 ≤ N ≤ 5 × 10^5, ~ 1≤D≤U≤10, ~ 1 ≤ S ≤ 500001, ~ 1 ≤ T_k ≤ 5 × 10^5, ~ 1 ≤ L_k ≤ 500001, ~ 1 ≤ M_k ≤ 4000$ 。