题目描述

厌倦了农场寒冷的冬天，奶牛贝西计划 飞往温暖的目的地度假。不幸的是，她 发现只有$\red{Bovinia}$航空公司愿意出售 奶牛票，这些票在 结构

波维尼亚航空公司拥有$\red{N}$架飞机（$\red{1}$$\red{<=N<=500）}$，每架飞机都在同一条航线上飞行 由两个或多个城市组成的特定"路线"。例如，一个 飞机可能从城市$\red{1}$开始飞行，然后飞往城市 $\red{5，}$然后飞到$\red{2}$号城市，最后飞到$\red{8}$号城市。没有城市 在路线中出现多次。如果贝西选择使用 她可以在沿途的任何城市登机，然后在 路线沿线的任何城市。她不需要在 第一个城市或在最后一个城市下船。每条路线都有一定的 费用，如果贝西使用路线的任何部分，她必须支付， 无论她沿途访问了多少城市，以及 贝西只能使用一条路线（也就是说，她不能使用 然后使用同一路线的不同部分）。

贝西想从她的农场找到最便宜的旅行方式 （在$\red{A}$市）前往她的热带目的地（$\red{B}$市）。因为她没有 想被复杂的行程弄糊涂，她想在 大多数有两条路线。请帮她决定她最低的花费是多少 必须付款。

$\red{[}$注意，这个问题与前面的问题之间的唯一区别是 铜牌的问题是贝西在这里最多可以使用两条路线，而不是 前一个问题中只有一条路径$\red{]}$

输入格式

第一行输入包含$\red{A}$、$\red{B}$和$\red{N，}$用空格分隔。

接下来的$\red{2N}$行描述了可用的路由，每行两行 路线第一行包含使用路由的成本（整数 范围$\red{1...}$$\red{1000）}$，以及沿线城市的数量（一个 范围为$\red{1...}$$\red{500). }$第二行包含 沿途城市井然有序。每个城市由一个 范围为$\red{1...}$$\red{10,000.}$

输出格式

输出一条行程的最小成本，该行程最多使用两条路线 贝西可以用来从$\red{A}$市到$\red{B}$市旅行。如果没有 解决方案，输出$\red{-1}$。

样例

输入样例

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

输出样例

7

提示

使用路线$\red{2}$从城市$\red{1}$行驶到城市$\red{3，}$然后使用路线$\red{1}$行驶 从城市$\red{3}$到城市$\red{2}$。