제시간에 도착하기

당신은 매우 바쁜 사람이라 중요한 회의가 많다. 오늘은 약속한 시각에 도착하는 것이 대단히 중요한 회의가 하나 있다.

다행히도 당신은 취리히에 살고 있고, 이곳에는 매우 정시에 다니는 트램 노선망이 잘 갖춰져 있다. 각 트램 노선은 한 장소에서 다른 장소로 일정한 간격으로 운행하며, 출발부터 도착까지 걸리는 시간은 항상 같다. 트램을 갈아타는 것은 매우 쉽고, 두 트램이 같은 정류장에 같은 시각에 있다면 갈아타는 데 시간이 걸리지 않는다고 가정한다. 즉 어떤 트램이 정확히 시각 $t$에 목적지에 도착하고 다른 트램이 같은 장소에서 시각 $t$ 또는 그 이후에 출발한다면, 충분히 갈아탈 수 있다.

당신은 지금 회의 전까지 호텔 방에서 일하고 있다. 매우 바쁜 사람이므로 회의에 제시간에 도착하면서 최대한 늦게 호텔을 나서고 싶다. 회의를 위해 언제 출발해야 하는가?

입력은 다음과 같다.

• 첫째 줄에 세 정수 $n$, $m$, $s$가 주어진다. ($2 \le n \leq 100\,000$, $1 \le m \leq 200\,000$, $1 \le s \leq 10^9$) $n$은 트램 정류장의 수, $m$은 트램 노선의 수, $s$는 지금부터 회의가 시작되는 시각(초)이다.
• 다음 $m$개 줄에 각각 다섯 정수 $u, v, t_0, p, d$가 주어진다. ($0 \le u \not= v < n$, $0 \le t_0 \le 10^9$, $1 \le p, d \le 10^9$) $i$번째 줄은 $i$번째 트램 노선을 나타내며, 이 노선은 정류장 $u$에서 출발해 정류장 $v$에 도착하고, 지금부터 $t_0$초 후에 첫 출발을 하며, 첫 출발 이후 $p$초마다 출발하고, 출발부터 도착까지 $d$초가 걸린다.

정류장은 $0$부터 $n - 1$까지 번호가 매겨져 있다. 당신의 호텔은 정류장 $0$에 있고, 회의는 정류장 $n - 1$에서 열린다.

회의에 제시간에 도착하면서 호텔을 나설 수 있는 가장 늦은 시각을 지금부터의 초 단위로 출력한다. 회의에 제시간에 도착할 수 없다면 impossible을 출력한다.