Home by trains#750
One of the teams participating in the Olympiad decided to return home by train. They want to get home as soon as possible. Unfortunately, not all trains go from the Olympiad city to the station where they live. Furthermore, not all trains passing through their station actually stop there (in general, trains do not stop at every station they pass).
All stations along the line are numbered from to . Station number is in the Olympiad city, and at time the team arrives at the station. The station they need to reach has number .
Write a program that, given the train schedule, calculates the minimum time by which the team can reach their home station.
The first line contains two numbers: (2 \leq n \leq 100) and (2 \leq e \leq n). The next line contains (0 \leq m \leq 100), the number of train routes. Then follow the descriptions of the routes. The description of each route begins with the integer k_i (2 \leq k_i \leq n) — the number of stations where the train stops, followed by k_i pairs of numbers: the first number in each pair is the station's number, and the second is the time when the train stops there (an integer between and 10^9). The stations within a single route are listed in increasing order of time. Each route goes only in one direction — either away from the Olympiad city or towards it.
Print a single number: the minimum time by which the team can reach their home station. If it is not possible to reach the destination using the given train routes, print -1.
Example 1
Example 5