qsgg and Subway

qsgg and Subway

题号：NC253382
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 $n$ 个地铁站，地铁站有 $m$ 条单向线路。

第 $i$ 条线路有个起点，途径 $k_i$ 个地铁站，发车周期为 $T_i$ 。

所有线路都在时刻 $0$ 时开始发车，之后每隔时间 $T_i$ 发车一次。

线路上，从地铁站到下一个地铁站所花费时间为 $1$ 。

时刻 $0$ 的时候，你在 $s$ 号地铁站，你想知道到达其他地铁站的最短时间。

注意：换乘不需要时间，你可以在 $t$ 时刻下地铁，搭乘在 $t$ 时刻到达该站的地铁。

输入描述:

输入共 $m+2$ 行。

第一行 $3$ 个整数 $n,m,s \ (1≤n,m≤10^6,1≤s≤n)$ ，分别表示地铁站数量，线路数量，初始起点。

接下来 $m$ 行，表示 $i$ 号线路。

首先 $2$ 个整数 $k_i,T_i\ (2≤k_i≤10^6,1≤T_i≤10^9)$ 表示线路途经地铁站数量，和发车周期。

接下来 $k$ 个整数表示途径地铁站编号，数据保证 $\sum \limits_{i=1}^{m}k_i ≤ 2\times10^6$ ，保证一条线路不存在两个相同的地铁站。

输出描述:

输出共  行，表示  表示到达  号地铁站的最短时间，若无法到达输出 。

示例1

输入

复制

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

输出

复制