Problem
올림피아드에 참가한 한 팀이 기차로 귀국하기로 결정했습니다. 동시에 사람들은 가능한 한 빨리 집에 가고 싶어합니다. 불행히도 모든 전기 열차가 올림피아드가 열리는 도시에서 남자들이 사는 역까지가는 것은 아닙니다. 그리고 더 불쾌한 것은 자신의 역을 지나는 모든 전기 열차가 정차하는 것은 아니라는 것입니다(또한 일반적으로 전기 열차는 지나가는 모든 역에 정차하지 않습니다).
선의 모든 역은 1부터 N까지 번호가 매겨져 있습니다. 동시에 1번 역은 올림피아드가 열리는 도시에 위치하고 있으며 시간 0에 선수들이 역에 도착합니다. 사람들이 가야 할 역의 번호는 E입니다.
기차 시간표가 주어졌을 때 남자들이 집에 있을 수 있는 최소 시간을 계산하는 프로그램을 작성하세요.
입력
입력 파일에서 숫자 N(2 ≤ N ≤ 100) 및 E(2 ≤ E ≤ N)가 먼저 기록됩니다. 그런 다음 숫자 M(0 ≤ M ≤ 100)이 쓰여져 열차 운행 횟수를 나타냅니다. 다음은 전기 열차의 M 여행에 대한 설명입니다. 각 기차 비행에 대한 설명은 숫자 Ki(2 ≤ Ki ≤ N) — 정차하는 역의 수, Ki 쌍의 숫자, 각 쌍의 첫 번째 숫자는 역 번호를 지정하고 두 번째 — 열차가 이 역에 정차하는 시간(시간은 0에서 109까지의 정수로 표현). 같은 항공편 내의 스테이션은 시간의 오름차순으로 정렬됩니다. 한 번 여행하는 동안 기차는 항상 같은 방향으로 움직입니다. 도시에서 멀어지거나 도시를 향합니다.
출력
파일을 출력하려면 하나의 숫자 인쇄 – 사람들이 자신의 역에 있을 수 있는 최소한의 시간. 기존 기차 노선으로 갈 수 없다면 –1을 인쇄하십시오.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
5 2
<사업부>2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |