e-olymp
Змагання

Azerbaijan Programming Olympiad - 2nd Stage preparation

Додому на електричках

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

Усі станції на лінії пронумеровані числами від 1 до n. При цьому станція номер 1 знаходиться у місті, де проводиться олімпіада, і у момент часу 0 діти приходять на станцію. Станція, на яку потрібно потрапити дітям, має номер e.

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

Вхідні дані

Спочатку записані числа n (2n100) та e (2en). Потім записано число m (0m100), яке позначає число рейсів електричок. Далі йде опис m рейсів електричок. Опис кожного рейсу електрички починається з числа ki (2kin) - кількості станцій, на яких вона зупиняється, а далі йде ki пар чисел, перше число кожної пари задає номер станції, друге - час, коли електричка зупиняється на цій станції (час виражається цілим числом з діапазону від 0 до 109). Станції всередині одного рейсу впорядковані у порядку зростання часу. Протягом одного рейсу електричка весь час рухається у одному напрямку - або від міста, або до міста.

Вихідні дані

Виведіть одне число - мінімальний час, через який діти зможуть опинитись на своїй станції. Якщо існуючими рейсами електричок вони дістатись не зможуть, виведіть -1.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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
Вихідні дані #1
20