상인

한 상인이 육지에서 최적의 여행 일정을 짜기가 너무 어려워서, 직선으로 흐르는 강을 따라 이동하며 물건을 팔기로 했다. 이 상인은 강 위의 어떤 위치에서 다른 어떤 위치로도 순식간에 이동할 수 있는 매우 빠른 보트를 가지고 있지만, 이 보트는 연료를 많이 쓴다. 강이 시작되는 쪽으로 거슬러 올라갈 때는 $1$미터당 $U$달러가 들고, 강을 따라 내려갈 때는 $1$미터당 $D$달러가 든다.

상인이 방문하려는 시장은 모두 $N$개이며, 각 시장은 단 하루만 열린다. 각 시장 $k$에 대해, 보트를 산 날을 기준으로 그 시장이 열리는 날 $T_k$, 강이 시작되는 지점으로부터 그 시장까지의 거리(미터) $L_k$, 그 시장을 방문하면 얻는 이익(달러) $M_k$가 주어진다. 강이 시작되는 지점으로부터 상인의 집까지의 거리는 $S$이다. 상인은 집에서 출발하여 원하는 시장들을 방문한 뒤 다시 집으로 돌아와 여행을 마친다.

상인이 이익을 최대로 얻으려면 어떤 시장들을 어떤 순서로 방문할지 정해야 한다. (시장을 하나도 방문하지 않아도 된다.) 상인이 얻는 전체 이익은 방문한 시장들에서 얻은 이익의 합에서 강을 오르내리는 데 든 연료 비용을 뺀 값이다.

두 시장을 모두 방문한다면, 방문 순서는 반드시 시장이 열리는 날짜 순서를 따라야 한다. 예를 들어 시장 $A$가 시장 $B$보다 먼저 열린다면, 시장 $B$를 먼저 방문한 뒤 시장 $A$를 방문할 수는 없다. 다만 두 시장이 같은 날 열린다면 둘을 임의의 순서로 방문할 수 있다. 하루에 방문할 수 있는 시장 수에는 제한이 없다. 같은 시장을 두 번 방문해 이익을 두 배로 얻을 수는 없지만, 이미 방문한 시장을 이익 없이 그냥 지나갈 수는 있다.

보트의 미터당 연료 비용, 상인의 집 위치, 각 시장이 열리는 날짜와 위치, 방문 시 얻는 이익이 주어질 때, 여행을 마친 뒤 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $N$, $U$, $D$, $S$가 공백 하나로 구분되어 차례대로 주어진다.

다음 $N$개의 줄에는 시장들의 정보가 특별한 순서 없이 주어진다. 이 중 $k$번째 줄에는 $k$번째 시장에 대한 세 정수 $T_k$, $L_k$, $M_k$가 공백 하나로 구분되어 차례대로 주어진다. 각각 시장이 열리는 날, 시장의 위치, 시장 방문 시 얻는 이익을 뜻한다.

모든 시장의 위치는 서로 다르며, 상인의 집 위치에서는 시장이 열리지 않는다. 즉, 어떤 두 시장도 같은 위치에서 열리지 않고 $L_k \ne S$이다.

• $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$ 방문 시 얻는 이익)

여행을 마친 뒤 얻을 수 있는 최대 이익을 정수 하나로 한 줄에 출력한다.

예제를 살펴보자. 집은 위치 $100$에 있고, 최적의 일정은 위치 $80$의 시장(둘째 날)과 위치 $75$의 시장(열째 날)을 방문하는 것이다. 방문 순서와 그때의 누적 이익은 다음과 같다.

• 강을 $20$미터 거슬러 올라가 위치 $80$으로 이동한다. 비용은 $5 \times 20 = 100$달러다. (누적 이익 $-100$)
• 위치 $80$의 시장을 방문해 $100$달러를 얻는다. (누적 이익 $0$)
• 강을 $5$미터 더 거슬러 올라가 위치 $75$로 이동한다. 비용은 $5 \times 5 = 25$달러다. (누적 이익 $-25$)
• 위치 $75$의 시장을 방문해 $150$달러를 얻는다. (누적 이익 $125$)
• 강을 $25$미터 따라 내려가 위치 $100$의 집으로 돌아온다. 비용은 $3 \times 25 = 75$달러다. (최종 이익 $50$)

따라서 최대 이익은 $50$달러다.