奶牛路线

奶牛贝西厌倦了农场里寒冷的冬天，她计划

飞往温暖的目的地度假。不幸的是，她

发现只有一家航空公司，波维尼亚航空，愿意出售

牛的票，这些票有点复杂

结构

波维尼亚航空公司拥有N架飞机（1架<=N<=500），每架飞机都在同一架飞机上飞行

由两个或多个城市组成的特定“路线”。例如，一个

飞机的飞行路线可能从城市1开始，然后飞往城市

5，然后飞到2号城市，最后飞到8号城市。没有城市

在路线中出现多次。如果贝西选择使用

她可以在沿途的任何城市登机，然后在

沿途的任何城市。她不需要在火车站登机

第一个城市或在最后一个城市下船。每一条路线都有一定的特点

成本，如果贝西使用路线的任何部分，

不管她沿途访问了多少城市。

贝西想从她的农场找到最便宜的旅行方式

（在A市）前往她的热带目的地（B市）。因为她没有

想被复杂的行程弄糊涂，她只想用

单一路线。请帮助她决定她需要的最低费用是多少

我必须付钱。

输入：（文件cowroute.in）

输入的第一行包含A、B和N，用空格分隔。

接下来的2N行描述了可用的路线，每行两行

路线第一行包含使用路由的成本（整数）

范围为1..1000），以及路线沿线的城市数量

范围为1..500的整数）。第二行包含

沿途城市井然有序。每个城市都由一个

范围为1..10000的整数。

样本输入：

1 2 3

3 3

3 2 1

4 4

2 1 4 3

8 5

4 1 7 8 2

输出：（文件cowroute.out）

输出贝西可以使用的单程旅行的最低成本

从A市到B市。如果没有这样的路线，输出-1。

样本输出：

解决方案说明：

虽然有更便宜的双路线解决方案（使用路线2旅行

从1号城市到3号城市，然后通过1号路线从3号城市到2号城市），

贝西只能使用一条路线，所以她必须使用3号路线

花费8英镑。