ТРОЛЕЙБУСНІ МАРШРУТИ#7821

ТРОЛЕЙБУСНІ МАРШРУТИ

1 секунда

64 мегабайти

Середня

Микола приїхав на обласну олімпіаду з інформатики. Вийшовши з вокзалу, він зрозумів, що запізнюється на початок туру. Микола вирішив якомога швидше доїхати до місця проведення олімпіади, скориставшись тим, що проїзд у тролейбусах міста для учасників олімпіади безкоштовний.

Відомо, що у місті існує $N$ зупинок, які обслуговуються $K$ тролейбусними маршрутами.

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

Початкові та кінцеві зупинки тролейбусів одного маршруту завжди різні, тобто маршрути не замкнені.

У нульовий момент часу $t = 0$ t = 0 з усіх кінцевих зупинок виїжджають тролейбуси. При цьому на кожному маршруті з кінцевих зупинок вирушають назустріч один одному два тролейбуси. Коли тролейбус приїжджає на кінцеву зупинку, одразу ж з цієї зупинки вирушає тролейбус у зворотному напрямі.

Микола знаходиться на зупинці $A$ і повинен дістатися до зупинки $B$ .

При цьому він може виходити з тролейбуса і пересідати на інший. У цьому випадку йому, можливо, доведеться чекати його. Час стоянки тролейбуса, висадки та посадки вважаємо рівними $0$ .

Визначте, через скільки хвилин Микола зможе дістатися до місця проведення олімпіади, або виведіть $- 1$ , якщо він не зможе потрапити на олімпіаду.

Вхідні дані

У першому рядку записані числа $N$ , $K$ $(3 \leq N \leq 100, 1 \leq K \leq 1000)$ (3 \leq N \leq 100,\, 1 \leq K \leq 1000).

У другому рядку записані номери зупинок $A$ та $B$ $(1 \leq A, B \leq N)$ (1 \leq A,\, B \leq N).

Наступні $K$ рядків містять описи кожного маршруту:

перше число $M_{i}$ M_i у рядку означає кількість зупинок тролейбусного маршруту; далі розташовано $M_{i} \times 2 - 1$ M_i \times 2 - 1 чисел, які описують номери зупинок маршруту та час руху між ними (номер зупинки; час руху до наступної зупинки; номер наступної зупинки; час руху до наступної зупинки; номер наступної зупинки і т.д.).

Всі числа цілі.

Вихідні дані

Час, який знадобиться Миколі, щоб доїхати до місця проведення олімпіади, або $- 1$ , якщо Микола не зможе дістатися до місця призначення.

Приклади

Приклад

8 3
1 8
4 1 2 5 2 7 2 8
4 2 1 5 1 6 2 8
5 3 8 8 1 7 2 6 4 4

Приклад 1

Примітка

Микола знаходиться на зупинці № $1$ , йому потрібно дістатися до зупинки № $8$ .

Існує три тролейбусних маршрути:

$1$ - $5$ - $7$ - $8$ (та зворотній $8$ - $7$ - $5$ - $1$ )

$2$ - $5$ - $6$ - $8$ (та зворотній $8$ - $6$ - $5$ - $2$ )

$3$ - $8$ - $7$ - $6$ - $4$ (та зворотній $4$ - $6$ - $7$ - $8$ - $3$ )

Микола виконує такі дії:

у $0$ момент часу ( $t = 0$ t = 0) сідає на зупинці № $1$ у тролейбус і через $2$ хвилини виходить на зупинці № $5$ ( $t = 2$ t = 2);
чекає хвилину і сідає на тролейбус, який прибуває із зупинки № $2$ ( $t = 3$ t = 3);
проїжджає одну зупинку і виходить на зупинці № $6$ ( $t = 4$ t = 4);
чекає дві хвилини, доки не прибуде тролейбус із зупинки № $4$ ( $t = 6$ t = 6);
сідає і їде до зупинки № $8$ ( $t = 10$ t = 10).