题目描述

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

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

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

输入格式

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

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

输出格式

输出贝西可以使用的单条路线的最小成本 从${A}$市到${B}$市。如果没有这样的路线，输出${-1}$。

样例

输入样例

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

输出样例

8

提示

虽然有更便宜的双路线解决方案（使用路线${2}$旅行 从城市${1}$到城市${3，}$然后从城市${3}$到城市${2}$的路线${1）}$， 贝西只能走一条路，所以她必须走${3}$号路 花费${8}$美元。