Міськтранс на честь дня свого народження вирішив провести змагання, і, за аналогією з «Мілом, що біжить» назвати їх «Місто, що їздить».

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

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

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

Формат вхідних даних

Спочатку вводиться число \(𝑁\) — загальна кількість контрольних пунктів (\(2≤𝑁 ≤10000\)).

Далі іде кількість автобусних маршрутів \(𝐾\) (\(1≤𝐾 ≤50000\)). Далі йде \(𝐾\) описів автобусних маршрутів.

Кожен маршрут описується чотирма числами \(𝐴_𝑖 , 𝐵_𝑖 , 𝐶_𝑖 , 𝐷_𝑖\) , які означають, що кожні \(𝐶_𝑖\) хвилин (тобто в моменти часу 0, \(𝐶_𝑖\) \(2 \times C_i...\)) автобус виходить з контрольного пункту \(𝐴_𝑖\) і через \(𝐷_𝑖\) хвилин прибуває до контрольному пункту \(𝐵_𝑖\). Всі \(𝐶_𝑖\) та \(𝐷_𝑖\) — натуральні і не перевищують 10000.

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

Далі вводиться число \(𝑀\) – кількість контрольних пунктів у маршрутному аркуші учасника (\(2≤𝑀≤50\)). Далі вводяться \(𝑀\) чисел \(𝑃_1 , 𝑃_2 , …, 𝑃_𝑀\) — номери контрольних пунктів, які потрібно відвідати (цифри в цьому списку можуть повторюватися). На момент часу 0 учасник знаходиться в пункті \(𝑃_1\) . Часом проходження маршруту вважається момент часу, коли учасник опиниться у пункті \(𝑃_𝑀\) .

Формат вихідних даних

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

Приклад вхідних даних

2 2
2 1 3 1
1 2 5 4
3
1 2 1

Приклад вихідних даних

7

Приклад вхідних даних

3 4
2 1 30 10
1 2 50 40
2 3 45 10
3 1 55 10
3
1 2 1

Приклад вихідних даних

65

Приклад вхідних даних

2 2
1 2 3 1
1 2 5 4
3
1 2 1

Приклад вихідних даних

-1