Устав от холодной зимы Беси хочет на каникулах слетать туда, где потеплее. Билеты коровам продаёт только 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.