성간 기차

2992년에는 대부분의 일자리를 로봇이 맡는다. 그래서 많은 사람이 여유 시간을 많이 갖게 되었고, 여러분의 가족도 성간 여행을 떠나기로 했다!

도달할 수 있는 행성은 $N$개이며 0번부터 $N-1$번까지 번호가 매겨져 있다. 성간 기차 노선은 $M$개다. $i$번 노선($0 \le i < M$)은 행성 $X[i]$에서 시각 $A[i]$에 출발해 행성 $Y[i]$에 시각 $B[i]$에 도착하며, 요금은 $C[i]$이다. 행성 사이를 오가는 수단은 기차뿐이다. 기차에서는 도착 행성에서만 내릴 수 있고, 같은 행성에서 바로 다음 기차를 타야 한다. 환승에는 시간이 걸리지 않는다. 형식적으로, 기차 열 $q[0], q[1], \dots, q[P]$가 유효한 것은 모든 $1 \le k \le P$에 대해 $Y[q[k-1]] = X[q[k]]$이고 $B[q[k-1]] \le A[q[k]]$일 때이다.

성간 여행은 오래 걸리므로 운賃 외에 식사 비용도 상당하다. 다행히 성간 기차는 식사를 무료로 무제한 제공한다. 즉, 노선 $i$를 타면 $A[i]$ 이상 $B[i]$ 이하의 어느 시각에든 비용 없이 원하는 만큼 식사를 할 수 있다. 다만 행성 $i$에서 다음 기차를 기다리는 동안 식사를 하면 식사 한 번마다 $T[i]$를 내야 한다.

가족은 식사를 $W$번 해야 한다. $i$번($0 \le i < W$) 식사는 $L[i]$ 이상 $R[i]$ 이하의 어느 시각에든 순간적으로 할 수 있다.

시각 0에 가족은 행성 0에 있다. 행성 $N-1$에 도착하는 데 드는 최소 비용을 구하라. 도달할 수 없으면 답은 $-1$이다.

• $2 \le N \le 10^5$.
• $0 \le M, W \le 10^5$.
• $0 \le X[i], Y[i] < N$, $X[i] \ne Y[i]$.
• $1 \le A[i] < B[i] \le 10^9$.
• $1 \le T[i], C[i] \le 10^9$.
• $1 \le L[i] \le R[i] \le 10^9$.