题目描述

厌倦了农场寒冷的冬天，奶牛贝西计划乘飞机去一个更温暖的地方度假。不幸的是，她发现只有一家航空公司——Air Bovinia愿意向奶牛出售机票，而且这些机票的结构有些复杂。

Air Bovinia拥有$N$架飞机（1 <= $N$ <= 500），每架飞机都有特定的“航线”，该航线由两个或更多城市组成。例如，一架飞机的航线可能从城市1出发，然后飞往城市5，接着飞往城市2，最后飞往城市8。任何城市在一条航线中都不会出现多次。如果贝西选择使用某条航线，她可以在该航线的任意一个城市登机，然后在该航线后续的任意一个城市下机。她不需要在第一个城市登机，也不需要在最后一个城市下机。每条航线都有一定的费用，贝西只要使用该航线的任何一部分，就必须支付这笔费用，无论她在该航线中经过多少个城市，而且贝西只能使用一条航线一次（也就是说，她不能先使用一条航线，之后再使用同一条航线的不同部分）。

贝西想找到从她的农场（位于城市$A$）到她的热带目的地（位于城市$B$）的最便宜的方式。由于她不想被复杂的行程弄糊涂，她最多只想使用两条航线。请帮助她确定她必须支付的最低费用。

[注意，这个问题与前面的铜牌问题的唯一区别是，这里贝西最多可以使用两条航线，而前面的问题中只能使用一条航线]

输入格式

• 第1行：输入包含三个空格分隔的整数$A$、$B$和$N$。
• 接下来$2N$行描述可用的航线，每条航线用两行描述。第一行包含使用该航线的费用（一个在1..1000范围内的整数）和该航线的城市数量（一个在1..500范围内的整数）。第二行包含该航线中按顺序排列的城市列表。每个城市由一个在1..10,000范围内的整数标识。

输出格式

• 第1行：输出贝西可以使用的、从城市$A$到城市$B$的、最多两条航线的行程的最低费用。如果没有这样的解决方案，输出-1。

样例

样例输入

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

样例输出

7

数据范围

1 <= $N$ <= 500，航线费用范围为1..1000，每条航线的城市数量范围为1..500，城市标识范围为1..10,000