시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 10 5 38.462%

문제

어떤 상인이 육지에서 최적 여행 스케줄을 구하는 것이 매우 어려웠기 때문에, 직선으로 흐르는 다뉴브강을 따라 이동하면서 물건을 팔기로 했다. 이 상인은 다뉴브 강을 따라 임의의 위치로부터 다른 임의의 위치로 순식간에 갈 수 있는 매우 빠른 보트를 가지고 있다. 그러나 이 보트는 연료 소비량이 매우 많다. 이 보트로 강이 시작되는 방향으로 거슬러 올라갈 때는 미터당 U 달러가 소비되고 강을 아래로 내려갈 때는 미터당 D 달러가 소비된다.

이 상인이 강을 따라 방문하고자 하는 시장이 N개 있으며 각 시장은 단 하루만 열린다. 각 시장 X에 대하여, 보트를 구입한 날을 기준으로 하여 이 시장이 열리는 날짜를 나타내는 Tx, 또한 강이 시작하는 곳으로부터 이 시장까지의 거리(미터) Lx, 이 시장을 방문하면 얻는 이익(달러) Mx를 알고 있다. 강이 시작하는 곳부터 상인이 사는 집까지의 거리는 S이다. 상인은 자기 집에서 출발하여 시장들을 방문한 다음 다시 자기 집으로 돌아와서 여행을 끝낸다.

시장을 방문하는 여행을 통해서 상인이 이익을 최대로 얻기 위해서, 어느 시장들을 선택하여 어떠한 순서대로 방문해야 할지를 결정하는 것을 도와주고자 한다. (선택하는 시장들이 전혀 없을 수도 있다.) 상인이 얻는 전체 이익은 시장들을 방문하여 얻는 이익의 합에서 강을 따라 오르내리는 데 드는 연료 비용을 뺀 것이다.

시장 A와 시장 B를 모두 방문할 경우, 이들 두 시장을 방문하는 순서는 시장이 열리는 날짜 순서대로임에 유의하라. 예를 들어 시장 A가 시장 B보다 먼저 열리면, 시장 B를 먼저 방문한 다음에 시장 A를 방문할 수는 없다. 그러나 두 시장이 같은 날에 열리면, 임의의 순서로 이들 두 시장을 방문할 수 있다. 하루에 방문할 수 있는 시장의 개수에는 제한이 없다. 두 배의 이익을 얻기 위해 같은 시장을 두 번 방문할 수는 없지만, 이미 방문한 시장을 이익을 얻지 않고 거쳐서 지나갈 수는 있다.

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

입력

표준 입력으로부터 다음의 데이터를 읽어야 한다 :

  • 첫 번째 줄에 정수들 N, U, D 와 S가 빈칸 하나를 사이에 두고 차례대로 주어진다.
  • 다음의 N 개의 줄에는 특별한 순서 없이 N개의 시장들에 대한 정보가 주어진다. 이들 N개의 줄 중 k번째 줄은 k번째 시장을 나타내며 이 줄에 세 개의 정수가 빈칸 하나를 사이에 두고 차례대로 주어진다 : 시장이 열리는 날 Tk, 시장의 위치 Lk, 시장을 방문할 때 얻는 이득 Mk.

유의 사항 : 입력으로 주어지는 위치들은 모두 다르다. 즉, 같은 장소에서 두 시장이 열리지 않으며 상인이 사는 장소에서는 시장이 열리지 않는다.

  • 1 ≤ N ≤ 500,000 시장의 개수
  • 1 ≤ D ≤ U ≤ 10 보트를 타고 강을 거슬러 올라갈 때 드는 미터당 비용 (U), 강을 따라 내려갈 때 드는 미터당 비용(D)
  • 1 ≤ S ≤ 500,001 상인이 살고 있는 집의 위치
  • 1 ≤ Tk ≤ 500,000 시장 k가 열리는 날
  • 1 ≤ Lk ≤ 500,001 시장 k의 위치
  • 1 ≤ Mk ≤ 4,000 시장 k를 방문할 때 얻는 이익

출력

표준 출력으로 여행을 끝낸 뒤 얻을 수 있는 최대 이득에 해당하는 하나의 정수를 한 줄에 출력해야 한다.

예제 입력

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

예제 출력

50

힌트

최적인 스케줄은 시장 1과 시장 3 (위치 80과 위치 75에 있는 시장들) 을 방문하는 것이다. 방문하는 순서와 이때 얻는 이익 및 비용은 다음과 같다:

  • 상인은 100 달러의 비용으로 강을 20미터 거슬러 위로 올라간다. 지금까지 이득 : -100
  • 시장 1을 방문하여 100달러 이익을 얻는다. 지금까지 이득 : 0
  • 25 달러의 비용으로 강을 5미터 거슬러 위로 올라간다. 지금까지 이득 : -25
  • 시장 3을 방문하여 150달러 이익을 얻는다. 지금까지 이득 : 125
  • 75 달러의 비용으로 강을 따라 25미터 아래로 내려가서 집에 돌아간다. 마지막 이득 : 50