Перевезення корів (Бронза)#11185

Перевезення корів (Бронза)

1 секунда

128 мегабайтів

Дуже легка

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

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

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

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

Вхідні дані

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

Наступні $2 n$ рядків описують доступні маршрути, по два рядки для кожного маршруту.

Перший рядок містить вартість використання маршруту (ціле число в діапазоні від $1$ до $1000$ ) та кількість міст на маршруті (ціле число в діапазоні від $1$ до $500$ ).

Другий рядок містить перелік міст у порядку слідування на маршруті. Кожне місто визначається цілим числом у діапазоні від $1$ до $10000$ .

Вихідні дані

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

Приклади

Хоча існує дешевше рішення з двома маршрутами (використання маршруту $2$ для подорожі з міста $1$ до міста $3$ , а потім маршруту $1$ для подорожі з міста $3$ до міста $2$ ), Бессі дозволено використовувати лише один маршрут. Тому вона повинна скористатися маршрутом $3$ , вартість якого становить $8$ .

Приклад 1