|In some country there are n cities numbered from 1 to n. There are also several types of flights between them. Each flight type is characterized with 5 integers A, B, F, T and P. All flights of this type depart from city A and arrive at city B (without changing planes in any intermediate cities). Each flight type is one-directional, so it is impossible to fly from city B to city A using the same flight type. All flights of the same type depart with some periodicity. More precisely, the first flight of this type departs from A at time F, the next flight departs at time F + P, then at F + 2P, and so on (there are infinitely many flights of the same type). Each flight of the same type has the same flight time T. I.e., if a plane departs from A at time T0, then it arrives to B at time T0 + T.
The description of all flight types is given in String flights. Concatenate the elements of this String in the same order as they are given without any delimiters between its elements to get a single String. This String will contain a single space separated list of flight type descriptions. Each such description will be of the form "A,B,F,T,P" (quotes for clarity), where the meaning of integers A, B, F, T and P is exactly the same as defined in the previous paragraph.
John would like to travel from city 1 to city n where his friend Brus is waiting for him. Unfortunately, there are no direct flights from 1 to n, so he will have to use several flights to reach city n. He can't use any other transport besides planes, so the departure city of each next flight he takes must be the same as the arrival city of the previous flight he has taken. Moreover, in order for him to be able to change planes, the departure time of each next flight must be strictly greater than the arrival time of the previous flight. If he arrives at some city at time T1 and then departs at time T2, the waiting time in this city is equal to T2 - T1. John defines the safety of his route from 1 to n as the minimum of waiting times over all cities where he changes flights.
John wants to arrive at city n no later than at time moment time. If there are several routes that achieve this goal, he wants to choose the route among them with the maximum possible safety. Return this maximum possible safety. If there are no such routes, return -1.
|-||n will be between 3 and 477, inclusive.|
|-||flights will contain between 1 and 47 elements, inclusive.|
|-||Each element of flights will contain between 1 and 47 characters, inclusive.|
|-||The concatenation of all elements of flights will be a single space separated list of flight type descriptions without leading or trailing spaces.|
|-||Each flight type description will be of form "A,B,F,T,P" (quotes for clarity), where A, B, F, T and P are integers formatted with no extra leading zeros.|
|-||In each flight type, A and B will be distinct integers between 1 and n, inclusive.|
|-||In each flight type, F, T and P will be between 1 and 1,000,000,000, inclusive.|
|-||There will be no flight from city 1 to city n.|
|-||time will be between 1 and 1,000,000,000, inclusive.|