The road network of Bajtogród consists of $n$ intersections connected by $m$ bidirectional roads. Each road connects two distinct intersections. Any two intersections are connected by at most one road. Roads may lead through tunnels and overpasses.

Intersection number 1 is the location of the school Bajtek attends, and intersection number $n$ is his home. In the morning, his parents drive him to school, but he returns home alone using public transport. The bus schedule has changed again this year. Since Bajtogród only uses single-use tickets validated upon each entry into a bus, Bajtek has decided to develop the fastest plan to return home with at most $k$ transfers. Help him!

Each bus of a given line travels along a fixed route, passing through certain intersections. It stops at each of these intersections, and one can enter or exit the bus there. Buses of a given line depart at regular time intervals (details are described in the Input section).

We assume that the time of: waiting at intersections, transferring from bus to bus (provided no waiting is required), * walking from the school to intersection number 1 and walking from intersection number $n$ to home is negligibly small.

Input

The first line of the input contains five integers $n, m, s, k$ and $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$), representing, respectively: the number of intersections, roads, and bus lines in Bajtogród, the maximum number of transfers Bajtek can make, and the minute he leaves school. Intersections are numbered from 1 to $n$.

The next $m$ lines contain descriptions of the roads; each contains three integers $a, b$ and $c$ ($1 \le a, b \le n, a \neq b, 1 \le c \le 10^9$), meaning that intersections $a$ and $b$ are connected by a bidirectional road, and traversing it (by any bus traveling along this road) takes $c$ minutes. Each unordered pair $\{a, b\}$ appears in the input at most once.

The next $2s$ lines contain descriptions of the bus lines; each description spans two lines. The first line of the description contains three integers $\ell, x$ and $y$ ($2 \le \ell \le n, 0 \le x \le 10^9, 1 \le y \le 10^9$), and the second line contains a sequence of pairwise distinct integers $v_1, v_2, \dots, v_\ell$ ($1 \le v_i \le n$). This means that the bus of the given line departs from intersection $v_1$ at minutes $x + j \cdot y$ for $j = 0, 1, 2, \dots$, and then travels sequentially through intersections $v_2, v_3, \dots, v_\ell$.

The sum of $\ell$ for all bus lines does not exceed $50\,000$.

Output

Your program should output a single line containing an integer representing the earliest minute at which Bajtek can reach home if he left school at minute $t$. If Bajtek cannot reach home at all, you should output the single word NIE instead.

Examples

Input 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

Output 1

8

Note

Explanation of the example: The figure above illustrates the road network of Bajtogród from the sample test. Circles represent intersections, and the numbers inside the circles are their IDs. Lines represent roads, and the numbers written next to them represent the travel time on that road. The route of bus line 1 is marked in red, while the route of bus line 2 is marked in blue.

Bajtek leaves school at minute $t = 1$, waits for bus line 2, which arrives at minute 2, takes it to intersection 3, where he transfers at minute 6 to bus line 1, which arrives at his home at minute 8.

For $k = 0$, Bajtek would have to wait at intersection 1 for bus line 1, which would depart at minute 10 and bring Bajtek home at minute 18.

Test cases

• Test case 1: $n = 10, m = 45, k = 10, t = 123$; intersections with IDs differing by 1 are connected by roads of length 1, and other pairs of intersections are connected by roads of length 100; buses start running from minute 0, transport between every pair of intersections with IDs differing by 1 or 2, and run every minute; the answer is 132.
• Test case 2: $n = 103, m = 102, k = 100, t = 0$; intersections with IDs differing by 1 are connected by roads of length 1, and other pairs of intersections are not connected directly; there is one bus that starts running at minute $10^9$ and goes through intersections $(1, 2, 3, \dots, n)$, and there are buses that start running at minute 0 and transport between every pair of intersections with IDs differing by 1 and finish their route; the answer is $10^9 + 102$.
• Test case 3: $n = 10\,000, m = 17\,891, s = 7891, k = 50, t = 0$; the answer is 11\,100\,000\,071.

Subtasks