Задача H. Домой на электричках ≡

Автор:X командный чемпионат Санкт-Петербурга по программированию - V Открытая Кировская командная олимпиада   Ограничение времени:2 сек
Входной файл:a.in   Ограничение памяти:8 Мб
Выходной файл:a.out  

Условие

Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, за которое ребятам удастся добраться домой.

Формат входного файла

Во входном файле записаны сначала числа N и E. Затем записано число M, обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

Формат выходного файла

В выходной файл выведите одно число - минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите -1.

Ограничения

2 ≤ E ≤ N ≤ 1000, 1 ≤ M ≤ 100, 2 ≤ Ki ≤ N.

Примеры тестов

№ Входной файл (a.in) Выходной файл (a.out)
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
 
20
0.034s 0.007s 15