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

1 号交叉路口旁是 Bajtek 就读的学校，而 $n$ 号交叉路口旁是他的家。早上父母会开车送他去学校，但他必须自己乘坐公共交通工具回家。今年公交时刻表又一次发生了变化。由于 Bajtogród 只使用单程票，且每次上车时都需要检票，Bajtek 决定制定一个回家的最快方案，要求换乘次数不超过 $k$ 次。请帮帮他！

每条公交线路的巴士都沿着固定的路线行驶，经过特定的交叉路口。在这些交叉路口中的每一个，巴士都会停靠，乘客可以上车或下车。同一线路的巴士以固定的时间间隔发车（详细信息见“输入格式”部分）。

我们假设以下时间可以忽略不计： 在交叉路口停留的时间； 换乘巴士的时间（前提是不需要等待）； * 从学校步行到 1 号交叉路口的时间，以及从 $n$ 号交叉路口步行到家的时间。

输入格式

输入的第一行包含五个整数 $n, m, s, k$ 和 $t$ ($2 \le n \le 10\,000, 1 \le m \le 50\,000, 1 \le s \le 25\,000, 0 \le k \le 100, 0 \le t \le 10^9$)，分别表示 Bajtogród 的交叉路口数量、道路数量、公交线路数量、Bajtek 最多可以换乘的次数，以及他离开学校的时间（分钟）。交叉路口编号为 $1$ 到 $n$。

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

接下来的 $2s$ 行包含公交线路的描述；每条线路的描述占用两行。第一行包含三个整数 $\ell, x$ 和 $y$ ($2 \le \ell \le n, 0 \le x \le 10^9, 1 \le y \le 10^9$)，第二行包含 $\ell$ 个互不相同的整数 $v_1, v_2, \dots, v_\ell$ ($1 \le v_i \le n$)。这意味着该线路的巴士在第 $x + j \cdot y$ 分钟从 $v_1$ 号交叉路口出发（其中 $j = 0, 1, 2, \dots$），然后依次经过 $v_2, v_3, \dots, v_\ell$ 号交叉路口。

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

输出格式

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

样例

样例输入 1

4 4 2 1 1
1 2 2
2 3 4
1 3 3
4 3 2
4 0 10
1 2 3 4
3 2 7
1 3 2

样例输出 1

8

说明

样例解释：上图展示了样例中的 Bajtogród 道路网。圆圈表示交叉路口，圆圈内的数字是其编号。连线表示道路，旁边的数字表示通过该道路所需的时间。1 号公交线路的路线用红色标出，2 号公交线路的路线用蓝色标出。

Bajtek 在 $t = 1$ 分钟离开学校，等待 2 号线公交车，该车在第 2 分钟到达，他乘坐该车前往 3 号交叉路口，并在第 6 分钟换乘 1 号线公交车，该车在第 8 分钟到达他家。

对于 $k = 0$，Bajtek 必须在 1 号交叉路口等待 1 号线公交车，该车在第 10 分钟出发，并在第 18 分钟将 Bajtek 送到家。

子任务