题目描述

奶牛贝茜想到一个更温暖的地方去度过这个寒冷的冬天。不幸的是，她发现只有一家名叫 AB 的航空公司愿意把票卖给奶牛，而且这些票的构成很奇怪。AB 有 N 架飞机，每架都有一个特定飞行路线，这个飞行路线包含 2 个或更多的城市。例如，一架飞机的路线可能是从城市 1 开始，然后飞到城市 6，再飞到城市 2，最后飞到城市 8。没有城市会在一条路线上出现多次。如果贝茜决定使用这个路线，她可以在一条路线的任意一个城市上飞机，然后在路线上任意一个城市下飞机。她不用一定在第一个城市上飞机，在最后一个城市下飞机。每条路线会有一个价格，不管贝茜沿途经过多少城市，她都要付这么多钱。

贝茜想找到从城市 A 到城市 B 的最小费用。由于她不想被复杂的行程困惑，她想只使用最多两条路线。请帮她决定她最少应该付多少钱。

输入格式

第一行包含三个整数 A、B、N，分别表示起点城市、终点城市和航线数量。

接下来描述 N 条航线，每条航线占两行：

• 第一行包含两个整数，分别表示该航线的费用和沿途城市的数量 m（2 ≤ m ≤ 500）。
• 第二行包含 m 个整数，表示按飞行顺序的城市列表（城市编号为整数，不重复）。

输出格式

输出一个整数，表示贝茜从城市 A 飞到城市 B 的最小费用（最多使用两条航线）。如果无法到达，输出 -1。

输入输出样例

输入样例 #1

1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2

输出样例 #1

7

样例解释 #1

贝茜可以使用两条航线：首先使用第二条航线从城市 1 飞到城市 3（路线：2,1,4,3，从城市 1 到城市 3），费用为 4；然后使用第一条航线从城市 3 飞到城市 2（路线：3,2,1，从城市 3 到城市 2），费用为 3。总费用为 7。

数据范围

• 1 ≤ N ≤ 10000。
• 每条航线的城市数量 m 满足 2 ≤ m ≤ 500。
• 航线费用为正整数，城市编号为整数（可能不连续）。