Problem
Salah satu pasukan yang mengambil bahagian dalam Olimpik memutuskan untuk pulang dengan kereta api. Pada masa yang sama, lelaki itu mahu pulang secepat mungkin. Malangnya, tidak semua kereta api elektrik pergi dari bandar tempat Olimpik diadakan ke stesen tempat mereka tinggal. Dan, yang lebih menyinggung, tidak semua kereta api elektrik yang melalui stesen mereka berhenti di situ (serta secara amnya, kereta api elektrik tidak berhenti di semua stesen yang mereka lalui).
Semua stesen dalam talian diberi nombor dari 1 hingga N. Pada masa yang sama, stesen nombor 1 terletak di bandar tempat Olimpik diadakan, dan pada masa 0 lelaki tiba di stesen. Stesen yang perlu dilawati oleh lelaki itu mempunyai nombor E.
Tulis program yang, berdasarkan jadual kereta api, mengira masa minimum apabila lelaki boleh berada di rumah.
Input
Dalam fail input nombor N (2 ≤ N≤ 100) dan E (2 ≤ E≤ N) ditulis dahulu. Kemudian nombor M (0 & le; M & le; 100) ditulis, menunjukkan bilangan larian kereta api. Berikut adalah penerangan tentang perjalanan M kereta api elektrik. Penerangan setiap penerbangan kereta api bermula dengan nombor Ki (2 ≤ Ki ≤ N) — bilangan stesen yang dihentikan, diikuti oleh pasangan nombor Ki, nombor pertama setiap pasangan menyatakan nombor stesen, &mdash kedua; masa apabila kereta api berhenti di stesen ini (masa dinyatakan sebagai integer dari 0 hingga 109). Stesen dalam penerbangan yang sama dipesan mengikut urutan masa menaik. Semasa satu perjalanan, kereta api bergerak ke arah yang sama sepanjang masa — sama ada jauh dari bandar atau ke arah bandar.
Output
Untuk mengeluarkan fail cetak satu nombor — masa minimum apabila lelaki boleh berada di stesen mereka. Jika mereka tidak boleh ke sana melalui laluan kereta api sedia ada, cetak –1.
Contoh
| # |
Input |
Output |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |