恒费跃迁仪

题目描述

研究所一共制造了 $n$ 种能量形态，编号为 $1$ 到 $n$，其中第 $i$ 种形态的稳定值为 $a_i$。

另外有 $m$ 台跃迁仪。对于一台记录为 $(u, v)$ 的跃迁仪，如果你当前处在形态 $u$，就可以用它切换到形态 $v$。

每次切换时，研究所都会按下面的方式结算能量消耗：

• 目标形态的稳定值减去当前形态的稳定值；
• 再额外收取固定的 $k$ 点调节能量。

也就是说，如果你从形态 $u$ 切换到形态 $v$，这一跳的消耗就是： $a_v - a_u + k$

你最初处在形态 $s$，目标是变成形态 $t$。

请你求出最小总消耗。如果无法达到目标形态，则输出 Impossible。

输入格式

第一行包含五个整数 $n, m, s, t, k$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示一台可用的跃迁仪。

输出格式

如果可以达到目标，输出最小总消耗；否则输出 Impossible。

输入输出样例 #1

输入 #1

4 4 1 4 2
5 8 3 10
1 2
2 4
1 3
3 4

输出 #1

9

输入输出样例 #2

输入 #2

3 1 1 3 5
10 6 20
1 2

输出 #2

Impossible

说明/提示

• 如果一条路径共经过了 $L$ 次切换，那么这条路径的总消耗中，固定调节能量一共会出现 $L$ 次。
• 请注意答案可能为负数。

数据范围

对于 $50\%$ 的数据，$1 \le n \le 1000$，$0 \le m \le 5000$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le m \le 2 \times 10^5$，$1 \le s, t, u, v \le n$，$1 \le k \le 10^9$，$1 \le a_i \le 10^9$。

建议

二刷、三刷