Description

Determine whether Ju Runguo can pass the final level without taking damage under the above conditions. If he can, output the minimum required health $B$ for Isaac under Ju Runguo’s control; otherwise, output 'IMP0SSBLE!!'.

Input Format

The first line contains five numbers $n, m, s, t, k$, representing that there are $n$ rooms in total, $m$ pairs of adjacent rooms together with the required health to traverse them, the start is $s$, the finish is $t$, and Isaac must arrive exactly at time $k$.

Each of the next $m$ lines contains three numbers $u, v, w$, meaning that room $u$ and room $v$ are adjacent, and the required health to traverse between the two rooms in both directions is $w$.

The next line contains a single number $a$, the number of monsters.

Then follow $a$ data blocks, each describing one monster’s roaming pattern.

In each block, the first number $T$ is the number of rooms in the monster’s roaming cycle, followed by $T$ room IDs that indicate that starting from time $0$, the monster will move from the first room in order and periodically repeat the sequence.

Output Format

Output a single line: the minimum required health $B$ for Isaac under Ju Runguo’s control, or 'IMP0SSBLE!!'.

2 1 1 2 1
1 2 1
0

1

2 1 1 2 1
1 2 2
0

2

2 1 1 2 10000001
1 2 2
0

2

2 1 1 2 10000001
1 2 2
1
2
2 1

2

Hint

There are $20$ groups of testdata.

For $15\%$ of the testdata, $a = 0$, $k \leq 20$.

For $25\%$ of the testdata, $a \leq 3$, $k \leq 1500$.

For $50\%$ of the testdata, $a \leq 3$, $k \leq 10^4$.

For $70\%$ of the testdata, $a \leq 20$, $k \leq 10^6$.

For $85\%$ of the testdata, $a \leq 30$, $k \leq 10^8$.

For $100\%$ of the testdata, $a \leq 30$, $k \leq 2*10^9$, $2 \leq T \leq 4$, $n \leq 50$, $m \leq 1250$.

All inputs are within the range of int.

All numbers are positive. There may be multiple edges; if an edge is given multiple times, the weight of its last occurrence prevails.

Translated by ChatGPT 5