题目描述

有 $N$ 条单向航线，每条给出按飞行顺序排列的不同城市和整条航线的票价。可以在任意一站上飞机，在其后任意一站下飞机，不论乘坐多少站都支付该航线的票价。求从城市 $A$ 到城市 $B$，最多乘坐两条航线的最小费用。

输入格式

第一行 $A,B,N$。接下来每条航线两行：第一行票价与城市数量 $k$；第二行 $k$ 个城市编号。

输出格式

输出最小费用，无解输出 -1。

样例

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

7

数据范围

对于40%的数据，$N\le5$；对于60%的数据，$N\le75$；对于100%的数据，$1\le N\le10000$，$2\le k\le500$。城市编号在1至1000之间，$A\ne B$，票价在1至 $10^9$ 之间。