One of the teams participating in the Olympiad decided to return home by train. At the same time, the guys want to get home as soon as possible. Unfortunately, not all electric trains go from the city where the Olympiad is held to the station where the guys live. And, what is even more offensive, not all electric trains that go past their station stop at it (as well as in general, electric trains do not stop at all the stations they pass by).
All stations on the line are numbered from 1 to N. At the same time, station number 1 is located in the city where the Olympiad is held, and at time 0 the guys arrive at the station. The station that the guys need to get to has the number E.
Write a program that, given a train schedule, calculates the minimum time when the guys can be at home.
Input
In the input file the numbers N (2 ≤ N ≤ 100) and E (2 ≤ E ≤ N) are written first. Then the number M (0 ≤ M ≤ 100) is written, indicating the number of train runs. The following is a description of M trips of electric trains. The description of each train flight begins with the number Ki (2 ≤ Ki ≤ N) — the number of stations it stops at, followed by Ki pairs of numbers, the first number of each pair specifies the station number, the second — time when the train stops at this station (time is expressed as an integer from 0 to 109). Stations within the same flight are ordered in ascending order of time. During one trip, the train moves in the same direction all the time — either away from the city or towards the city.
Output
To output file print one number — the minimum time when the guys can be at their station. If they can't get there by existing train routes, print –1.
Examples
| # |
Input |
Output |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |