题目描述

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

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

输入格式

​第1行包含3个数字A、B和N。

下面的2N行，描述可用的路线，每条路线的描述占两行。第一条路线包含路线费用，以及沿途有多少个城市(不超过500个)。第2行包含一个按顺序的城市的列表。

输出格式

输出贝茜用一条飞行路线从城市A飞到城市B的最小费用。如果没有这样的路线，输出“-1”。

样例数据

input

1 2 3

3 3

3 2 1

4 4

2 1 4 3

8 5

4 1 7 8 2

output

8

样例解释

尽管这里有一个更便宜的用两条线路的方案(用路线2从城市1到城市3，再用路线1从城市3到城市2)，贝茜只被允许用一条线路，所以她必须花到城市8的费用使用3号线路。

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$