루미 알고리즘

#1499골드Walkways

PO 2020 온라인 예선코딩출제 Hugo Eberhard영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The Swedish team for the International Olympiad in Informatics has just landed in Singapore to compete in IOI 2020. On the way to the baggage claim, they have to pass through a long corridor with several moving walkways. The corridor is M meters long, and the team is currently at the beginning of it, trying to figure out how quickly they can reach the baggage claim. There are N moving walkways in the corridor. Each walkway starts at a certain distance from the beginning of the corridor, ends at a certain distance from the beginning of the corridor, and takes a certain amount of time to travel along. All walkways move in the direction of the corridor, and one can only step onto a walkway at the beginning of it and step off at the end of it. When the team is not on any walkway, it takes g seconds to walk one meter. The corridor and walkways are narrow enough that only the time it takes to travel parallel to the corridor matters. Therefore, if one walkway ends at the same distance from the beginning as another walkway starts, it takes no time to move between the walkways. If the team plan their route optimally, how fast can they reach the end of the corridor?

Note that it may be advantageous to sometimes walk backward through the corridor to reach a walkway that takes one further ahead. However, there are no walkways going backward through the corridor.

Input

The first line of input contains three integers N, M and g (1 ≤ N ≤ 2 · 10^5, 2 ≤ M ≤ 2 · 10^5, 1 ≤ g ≤ 100), the number of walkways, the length of the corridor in meters and the speed of the team in seconds per meter.

The following N lines each contain three integers describing a walkway, s_i, e_i and t_i (1 ≤ s_i < e_i ≤ M,1 ≤ t_i ≤ 100), the number of meters from the start of the corridor to the start of the walkway, the number of meters from the start of the corridor to the end of the walkway and how long it takes to use the walkway.

Output

Print an integer: how long it will take for the team to reach the end of the corridor if they plan their route optimally.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

GroupPoint valueConstraints
18N,M ≤ 10 and you never have to go backwards.
213N,M ≤ 1000 and you never have to go backwards.
340You never have to go backwards.
415N,M ≤ 1000
524No further constraints.

Explanation of Samples

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Sample 1

In sample 1, it takes 2 seconds to walk one meter when the team is not on a walkway. The fastest way to reach the end is to walk to the walkway that takes 5 seconds, use it, then walk to the walkway that takes 2 seconds and use it. In total, this takes 4+5+2+2=13 seconds.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 2: Sample 2

In sample 2, it instead takes 5 seconds to walk one meter when the team is not on a walkway. The fastest way to reach the end is to walk to the walkway that takes 8 seconds, use it, and then go back one meter to use the walkway that takes 2 seconds, and then walk the final meter. In total, this takes 5+8+5+2+5=25 seconds.

예제

예제 1

입력
4 9 2
2 5 5
1 7 8
4 7 4
6 9 2
출력
13

예제 2

입력
4 9 5
1 6 8
6 9 13
1 3 5
5 8 2
출력
25

출처 표기

출처: Programmeringsolympiaden 2020년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.