Маршрутизація корів II
Утомившись від холодної зими, Бессі вирішила провести канікули в теплішому місці. Квитки для корів продає лише авіакомпанія Air Bovinia.
Air Bovinia має n літаків, кожен з яких обслуговує певний маршрут, що включає два або більше міст. Наприклад, літак може почати свій маршрут у місті 1, потім летіти до міста 5, далі до міста 2, і завершити маршрут у місті 8. Жодне місто не повторюється в маршруті. Обравши маршрут, Бессі може сісти на нього в будь-якому місті цього маршруту і вийти в будь-якому з наступних міст. Вона не зобов'язана починати з першого міста чи закінчувати в останньому. Кожен маршрут має фіксовану вартість, яку Бессі повинна сплатити, якщо вона використовує будь-яку частину маршруту, незалежно від кількості відвіданих міст. Крім того, Бессі може скористатися кожним маршрутом лише один раз, тобто вона не може використовувати частину маршруту, а потім пізніше іншу частину того ж маршруту.
Бессі прагне знайти найдешевший спосіб дістатися від своєї ферми (місто A) до свого "теплого місця" (місто B), використовуючи не більше ніж два маршрути. Допоможіть їй визначити мінімальну вартість подорожі.
Зверніть увагу, що відмінність цієї задачі від попередньої полягає в тому, що Бессі може використовувати до двох маршрутів, а не лише один.
Вхідні дані
Перший рядок містить A, B, n (1 ≤ n ≤ 500). Наступні 2n рядків описують доступні маршрути, по два рядки на маршрут. Перший рядок містить вартість маршруту (ціле число від 1 до 1000) і кількість міст у цьому маршруті (ціле число від 1 до 500). Другий рядок містить список міст у порядку їх проходження в маршруті. Кожне місто ідентифікується цілим числом у діапазоні від 1 до 10000.
Вихідні дані
Виведіть мінімальну вартість подорожі з A в B, використовуючи не більше ніж два маршрути. Якщо такого рішення немає, виведіть -1.
Приклад
Використовуючи маршрут 2, добираємося від міста 1 до міста 3, а потім за допомогою маршруту 1 подорожуємо з міста 3 в місто 2.