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

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

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

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

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

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

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

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

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

Input

У першому рядку записані числа N, K (3 ≤ N ≤ 100, 1 ≤ K ≤ 1000).У другому рядку записані номери зупинок А та В (1 ≤ A, B ≤ N).Наступні K рядків містять описи кожного маршруту:перше число M[i] у рядку означає кількість зупинок тролейбусного маршруту; далі розташовано M[i] * 2 - 1 чисел, які описують номери зупинок маршруту та час руху між ними (номер зупинки; час руху до наступної зупинки; номер наступної зупинки; час руху до наступної зупинки; номер наступної зупинки і т.д.).Всі числа цілі.

У першому рядку записані числа N, K (3 <= N <= 100, 1 <= K <= 1000).У другому рядку записані номери зупинок А та В (1 <= A, B <= N).Наступні K рядків містять описи кожного маршруту:перше число M[i] у рядку означає кількість зупинок тролейбусного маршруту; далі розташовано M[i]*2 - 1 чисел, які описують номери зупинок маршруту та час руху між ними (номер зупинки; час руху до наступної зупинки; номер наступної зупинки; час руху до наступної зупинки; номер наступної зупинки і т.д.).Всі числа цілі.

Output

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

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

Examples

Note

Микола знаходиться на зупинці №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) сідає на зупинці №1 у тролейбус і через 2 хвилини виходить на зупинці №5 (t = 2);

● чекає хвилину і сідає на тролейбус, який прибуває із зупинки №2 (t = 3);

● проїжджає одну зупинку і виходить на зупинці №6 (t = 4);

● чекає дві хвилини, доки не прибуде тролейбус із зупинки №4 (t = 6);

● сідає і їде до зупинки №8 (t = 10).

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

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

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

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

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

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

Визначте через скільки хвилин Микола зможе дістатися до місця проведення олімпіади, або виведіть -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) сідає на зупинці №1 у тролейбус і через 2 хвилини виходить на зупинці №5 (t = 2);

● чекає хвилину і сідає на тролейбус, який прибуває із зупинки №2 (t = 3);

● проїжджає одну зупинку і виходить на зупинці №6 (t = 4);

● чекає дві хвилини, доки не прибуде тролейбус із зупинки №4 (t = 6);

● сідає і їде до зупинки №8 (t = 10).