Маршрути Корів II#11186

Маршрути Корів II

1 секунда

128 мегабайтів

Складна

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

Air Bovinia володіє $n$ літаками, кожен з яких літає за певним "маршрутом", що складається з двох або більше міст. Наприклад, один літак може летіти за маршрутом, який починається в місті $1$ , потім летить до міста $5$ , потім до міста $2$ , і нарешті до міста $8$ . Жодне місто не з'являється на маршруті більше одного разу.

Якщо Бессі вирішує скористатися маршрутом, вона може сісти на літак у будь-якому місті вздовж маршруту, а потім вийти в будь-якому місті, яке з'являється пізніше на маршруті. Їй не обов'язково сідати у перше місто чи виходити в останньому місті. Кожен маршрут має фіксовану вартість, яку Бессі повинна сплатити, якщо вона використовує будь-яку частину цього маршруту, незалежно від того, скільки міст вона відвідує вздовж нього. Крім того, Бессі може використати кожен маршрут щонайбільше один раз (тобто вона не може використати одну частину маршруту, а пізніше використати іншу частину того самого маршруту).

Бессі хоче знайти найдешевший спосіб дістатися зі своєї ферми, розташованої в місті $A$ , до свого тропічного пункту призначення, розташованого в місті $B$ . Оскільки вона не хоче мати справу зі складним маршрутом, вона хоче використати щонайбільше два маршрути. Будь ласка, допоможіть їй визначити мінімальну загальну вартість, яку вона повинна сплатити.

Вхідні дані

Перший рядок містить $A, B$ та $n (1 \leq n \leq 500)$ n~(1 \le n \le 500).

Наступні $2 n$ рядків описують доступні маршрути, по два рядки на маршрут. Перший рядок містить вартість використання маршруту (ціле число від $1$ до $1000$ ) та кількість міст вздовж маршруту (ціле число від $1$ до $500$ ). Другий рядок містить список міст у порядку, в якому вони з'являються вздовж маршруту. Кожне місто ідентифікується цілим числом у діапазоні від $1$ до $10000$ .

Вихідні дані

Виведіть мінімальну вартість маршруту, що використовує щонайбільше два маршрути, який дозволяє Бессі подорожувати з міста $A$ до міста $B$ . Якщо такого маршруту не існує, виведіть $- 1$ .

Приклади

Використайте маршрут $2$ , щоб дістатися з міста $1$ до міста $3$ , а потім використайте маршрут $1$ , щоб дістатися з міста $3$ до міста $2$ .

Приклад 1

Примітка

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