Задача H. Светофоры ≡

Условие

Студент Вася каждый день ездит на машине в университет учиться. Система дорог города, в котором живет Вася, представляет собой на карте прямоугольную сетку состоящую из N × M перекрестков. Дом, от которого отъезжает Вася, находится в левом верхнем углу карты, а университет — в правом нижнем углу.

Все перекрёстки снабжены светофорами, работающими в необычном режиме. По всем направлениям перекрёстка одновременно горит либо зелёный, либо красный свет.

Вася уже давно ездит по этим дорогам и для каждого светофора знает все промежутки времени, когда он светит красным.

Итак, Васе нужно успеть на первую пару! Но Вася — порядочный гражданин и не станет проезжать на красный свет. В то же время, скорость автомобиля и состояние дорог в городе позволяют ему перемещаться между светофорами настолько быстро, что временем перемещения можно пренебречь. (Т. е. время проезда между перекрёстками равно нулю).

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

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

Входной файл содержит 2 целых числа N M.

Далее следует N × M расписаний светофоров, перечисленных в порядке обхода карты построчно. Первое число i − го расписания c_i — количество временных отрезков i − го светофора, за которым следует c_i пар целых чисел  — временные отрезки, когда i − ый светофор светит красным. Отрезки не пересекаются и отсортированы по возрастанию левой границы.

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

Выходной файл должен содержать единственное целое число — момент времени, когда Вася приедет в университет.

Ограничения

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

2 2
1 0 1
1 0 1
1 0 1
1 0 1

1

2 3
2 0 1 4 10
2 0 3 4 10
2 0 1 3 10
1 0 100
1 0 100   
1 0 100 

10