Bajtogród 的路网由$n$ 个路口和 $m$ 条双向道路组成。每条道路连接两个不同的路口，且任意两个路口之间最多只有一条直接道路。道路可能经过隧道或高架桥。

路口 $1$ 附近有一所学校，Bajtek 每天在那里上学，而路口 $n$ 附近是他的家。早上，父母会开车送他去学校，但放学后他需要自己乘坐公共交通回家。今年公交车的时刻表又一次调整了。由于 Bajtogród 只提供单程票，每次上车都需要检票，Bajtek 决定制定一个最快的回家计划，且换乘次数不超过 $k$ 次。请你帮帮他！

每条公交线路的车辆都会按照固定的路线行驶，经过某些路口，并在每个路口停靠，供乘客上下车。同一线路的公交车会按照固定的时间间隔发车（具体细节见输入格式）。我们假设以下时间可以忽略不计：

公交车在路口的停靠时间；

从一辆公交车换乘到另一辆公交车的时间（假设无需等待）；

从学校走到路口 $1 $以及从路口 $n$ 走回家的时间。

输入的第一行包含五个整数 $n, m, s, k, t (2 \leq n \leq 10000, 1 \leq m \leq 50000, 1 \leq s \leq 25000, 0 \leq k \leq 100, 0 \leq t \leq 10^{9})$，分别表示路口数量、道路数量、公交线路数量、Bajtek 最多允许的换乘次数，以及他离开学校的分钟数。路口编号从 $1$ 到$ n$。

接下来的 $m$ 行描述道路，每行包含三个整数 $a, b, c (1 \leq a, b \leq n, a \neq b, 1 \leq c \leq 10^{9})$，表示编号为 $a$ 和 $b$ 的路口之间有一条双向道路，乘坐任何经过这条路的公交车通过它需要 $c$ 分钟。每对无序路口对$ \{a, b\}$ 在输入中最多出现一次。

接下来的 $2s$ 行描述公交线路，每条线路的描述占用两行。第一行包含三个整数 $\ell, x, y (2 \leq \ell \leq n, 0 \leq x \leq 10^9, 1 \leq y \leq 10^9)$，第二行包含 $\ell$个两两不同的整数 $v_1, v_2, ... , v\ell (1 \leq v_i \leq n)$。这表示该线路的公交车从路口 $v_1$ 在$ x + j · y (j = 0, 1, 2, ...) $分钟发车，然后依次经过路口 $v_2, v_3, ... , v\ell$。保证对于 $1 \leq i < l$，路口$ v_i$ 和$ vi+1$ 之间存在一条道路。

所有公交线路的$ \ell$ 之和不超过 $50000$。

你的程序应输出一行，包含一个整数，表示 Bajtek 从学校离开后能到达家的最早分钟数。如果 Bajtek 无法在 $t$ 分钟后回家，则应输出 $NIE$。