Problem H
Arriving on Time
Luckily you live in Zürich, which features a large network of extremely punctual trams. Each tram line travels from one place to another at regular intervals, always taking the same time from departure to arrival. It is very easy to change trams, and we assume that it takes no time to change to another tram if both are at a stop at the same time. This means that if a tram arrives at its destination at exactly time $t$ and another tram departs from the same place at time $t$ (or later), you will have enough time to change tram.
You are currently working in your hotel room before the meeting. Since you are a very busy person, you would like to leave your hotel at the latest possible time possible while still ariving to the meeting on time. When do you need to leave for your meeting?
Input
The input consists of:
-
one line with three integers $n$, $m$ and $s$ ($2 \le n \leq 100\, 000$, $1 \le m \leq 200\, 000$, $1 \le s \leq 10^9$), the number of tram stops, the number of tram lines, and the time at which the meeting starts in seconds relative to now.
-
$m$ lines, each with five integers $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$). The $i$’th line describes the $i$’th tram line, which departs from tram stop $u$, arrives at tram stop $v$, starts its first departure $t_0$ seconds from now, departs every $p$ seconds from the first departure, and takes $d$ seconds from departure to arrival.
The stops are numbered between $0$ and $n - 1$. Your hotel is located at stop $0$, and the meeting is at stop $n - 1$.
Output
Output the latest time at which you can leave the hotel while arriving to your meeting on time, in seconds from now. If you can not make it to your meeting on time, output impossible instead.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 10 0 1 1 2 6 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 5 0 1 1 1 5 |
impossible |
