상인 timer 1초 memory 128MB

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

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

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

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

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