Problem
オリンピアードに参加しているチームの 1 つが、電車で帰宅することにしました。同時に、男たちはできるだけ早く家に帰りたいと思っています。残念ながら、すべての電車がオリンピックが開催される都市から男たちが住んでいる駅まで行くわけではありません。さらに不快なことに、駅を通過するすべての電車がその駅に停車するわけではありません (一般的に、電車は通過するすべての駅に停車するわけではありません)。
路線上のすべての駅には 1 から N までの番号が付けられています。同時に、駅番号 1 はオリンピックが開催される都市にあり、時刻 0 に男たちは駅に到着します。男たちが行く必要がある駅の番号は E です。
与えられた電車の時刻表から、男性が家にいることができる最短時間を計算するプログラムを作成してください。
入力
入力ファイル内 数字 N (2 ≤ N ≤ 100) と E (2 ≤ E ≤ N) が最初に書かれます。次に、M (0 ≤ M ≤ 100) という数字が書かれ、列車の走行回数を示します。以下、電車のMトリップについて説明します。各列車のフライトの説明は、番号 Ki (2 ≤ Ki ≤ N) — で始まります。停車する駅の数、その後に Ki のペアの数字が続きます。各ペアの最初の数字は駅番号を指定し、2 番目の数字は駅番号を指定します —列車がこの駅に停車する時刻 (時刻は 0 から 109 の整数で表されます)。同じフライト内のステーションは、時間の昇順で並べられています。 1 回の旅行中、列車は常に同じ方向に移動します。街から離れても、街に向かっても。
出力
出力ファイルへ 数値を 1 つ表示 —男が駅にいることができる最小時間。既存の電車のルートでそこにたどり着けない場合は、–1 と出力してください。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |