Problem K
Compensation

In the free-market, ruthlessly capitalist world of train fares, only one thing matters: incentives.

Train companies are incentivised with bonuses for high throughput, successful journeys, and customer satisfaction. Conversely, the companies are disincentivised from failure via mandatory refunds for customers delayed by $30$ minutes or more.

Being a ruthless capitalist yourself, you have decided to take advantage of this generous delay compensation provision.

The refund is awarded provided that no matter the combination of trains you had taken (provided they followed the same route of stations as planned), you would still be unable to reach your destination in strictly less time than $30$ minutes (or $1800$ seconds), of the time you would have arrived assuming your booked journey was exactly on time.

Armed with your printout of the day’s delays, and the original timetable, you must ask yourself only one question: what is the earliest time you can book a train for from station $1$, in order to earn this restitutive reward?

Input

• One line containing two integers: $N$ ($1 \le N \le 100$), the number of stations, and $M$ ($1 \le M \le 10^5$), the number of scheduled trains.

• The next $M$ lines each contain 4 integers:

  • $X$, the starting station ($1 \le X \le N-1$),

  • $S$ and $T$ ($0 \le S \le T < 86\, 400$), the planned departure and arrival times in seconds,

  • and $L$ ($0 \le L < 86\, 400$), the duration by which the train’s departure and arrival times are delayed.

Stations are numbered from $1$ to $N$ in the order you will visit them. Each train goes between stations $X$ and $X+1$. It is possible to change between trains instantanesouly.

Output

• One line containing one integer: the start time of the earliest train journey you could book in order to earn your compensation, or impossible if no such journey is possible.

2 3
1 1800 9000 1800
1 2000 9200 1600
1 2200 9400 1400

1800

2 2
1 1800 3600 1800
1 1900 3600 1600

impossible

3 2
1 10 20 1
2 20 30 0

10