cowroute2

题目背景

Input file: cowroute2.in Output file: cowroute2.out Time limit: 1s Memory limit: 256M Bessie 想到一个更温暖的地方去度过这个寒冷的冬天。不幸的是，她发现只有一家名叫 Air Bovinia 的航空公司愿意把票卖给奶牛；而且这些票的构成有些奇怪。 Air Bovinia 拥有 N 只飞机，每只都有一个特定的“飞行路线”，这个飞行路线包含 2 个或更多的城 市。例如，一架飞机的路线可能是从城市 1 开始，然后飞到城市 5，再飞到城市 2，最后飞到城市 8。没 有城市会在一条路线上出现多次。如果 Bessie 决定使用这个路线，她可以在一条路线的任意一个城市上 飞机，然后在路线上任意一个城市下飞机。她不用一定在第一个城市上飞机，在最后一个城市下飞机。每 条路线会有一个价格，不管 Bessie 沿途经过多少城市，她都要付这么多钱。 Bessie 想找到最近的从城市 A 到城市 B 的距离。由于她不想被复杂的行程困惑，她想只使用最多 两条路线。请帮她决定她最少应该付多少钱。 【注意这道题和上一道题目唯一的区别是 Bessie 可以使用最多两条路线】

题目描述

输入格式

第一行包含 3 个数字 A, B, N. 下面 2N 行描述可用的路线，每条路线的描述占两行。第一条路线包含路线费用，以及沿途有多少 个城市（不超过 500 个）。第二行包含一个按顺序的城市的列表。每个城市用一个数字表示，不会超过 10000.

输出格式

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

样例 #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

提示

Explanation 用路线 2 从城市 1 到城市 3，再用路线 1 从城市 3 到城市 2。 Scoring • 对于 40% 的数据，N ≤ 5。 • 对于 60% 的数据，N ≤ 75。