33891번 - 구간 단속 종료 지점입니다 스페셜 저지

2025 아주대학교 프로그래밍 경시대회가 끝난 후, 현빈이는 차를 타고 본가에 내려가는 중이다.

현빈이가 본가로 가는 경로는 일직선으로 나타낼 수 있으며, 학교는 $x=0$에, 본가는 $x=E$에 위치하고 있다. 현빈이가 운전하는 차의 속력은 $M$을 넘을 수 없다.

본가로 향하는 길에는 총 $N$개의 구간 단속 지점이 있다. $i(1\leq i\leq N)$번째 구간 단속 지점 $[s_i,e_i)$는 $x=s_i$에서 시작하고 $x=e_i$에서 종료되며, 구간을 지나는 평균 속도는 $v_i$를 초과해서는 안 된다.

학교의 위치인 $x=0$에서 출발하여 현빈이의 본가인 $x=E$에 도착하는데 걸린 최소 시간을 구해보자.

단, 현빈이의 차가 가속과 감속을 하는 데는 시간이 걸리지 않는다.

첫 번째 줄에 구간 단속 지점의 수 $N$, 현빈이가 운전하는 차의 최대 속력 $M$, 현빈이의 본가 위치 $E$가 공백으로 구분되어 주어진다. $(1\leq N\leq 500\,000;$ $1\leq M \leq 1\,235;$ $1 \leq E \leq 10^{9})$

두 번째 줄부터 $N$개 줄에 걸쳐 구간 단속 지점에 대한 정보 $s_i, e_i, v_i$가 공백으로 구분되어 주어진다. $(0\leq s_i < e_i \leq E;$ $1\leq v_i \leq M)$

입력으로 주어지는 모든 수는 정수이다.

현빈이가 본가에 도착하는데 걸린 최소 시간을 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.

• $x=s$를 통과하는 시점이 $t_1$이고 $x=e$를 통과하는 시점이 $t_2$라고 할 때, 구간 $[s,e)$의 평균 속도 $\bar{v}$는 다음과 같다. $$\bar{v}=\frac{e-s}{t_2-t_1}$$
• 현빈이의 집은 용인시 수지구로, 고작 차로 10분 거리라고 한다.