e-olymp
Yarışlar

Azerbaijan Programming Olympiad - 2nd Stage preparation

Elektrik qatarları ilə evə

Olimpiada iştirakçı-komandalardan biri evə elektrik qatarı ilə qayıtmaq qərarına gəldi. Bu zaman uşaqlar evə mümkün qədər tez çatmaq istəyirlər. Təəssüf ki, heç də bütün qatarlar olimpiadanın keçirildiyi şəhərdən uşaqların yaşadıqları stansiyaya qədər getmir. Daha təəssüf doğuran odur ki, heç də bütün qatarlar onların stansiyasından keçərkən orada dayanmır (ümumiyyətlə, qatarlar yanından keçdikləri stansiyaların heç də hamısının uzaqlığında dayanmırlar).

Xətdəki bütün stansiyalar 1-dən n-ə qədər nömrələnmişdir. Bu zaman 1 nömrəli stansiya olimpiadanın olduğu şəhərdə yerləşir və 0 zamanında uşaqlar stansiyaya gəlirlər. Uşaqların gəlmək istədikləri stansiyanın nömrəsi e-dir.

Elektrik qatarlarının verilmiş hərəkət qrafikinə görə uşaqların evə çata biləcəkləri minimal zamanı hesablayan proqramı tərtib edin.

Giriş verilənləri

Giriş faylında əvvəlcə n (2n100) və e (2en) ədədləri verilir. Sonra qatarların reyslərinin sayını ifadə edən m (0m100) ədədi verilir. Daha sonra qatarların m reysinin təsviri verilir. Qatarın hər bir reysinin təsviri onun dayandığı stansiyaların sayını ifadə edən ki (2kin) ədədi ilə başlayır, daha sonra ki ədəd cütlüyü verilir, hər bir cütlüyün birinci ədədi stansiyanın nömrəsini, ikincisi - qatarın bu stansiyada dayanacağı zamanı (zaman 0-dan 109-a qədər tam ədədlə verilir) ifadə edir. Bir reys daxilində stansiyalar zamana görə artan sira ilə sıralanmışdır. Bir reys ərzində qatar həmişə bir istiqamətdə hərəkət edir - ya şəhərdən, ya da şəhərə doğru.

Çıxış verilənləri

Çıxış faylına yeganə ədədi - uşaqların öz stansiyalarına çata biləcəkləri minimal zamanı verin. Əgər qatarların mövcud reysləri ilə onlar evə çata bilməyəcəklərsə, -1 verin.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
Çıxış verilənləri #1
20