补给能源

核心缓存区的第五层，是一片荒漠。不是火星的荒漠——是Zero记忆中的地球荒漠，黄沙漫天，寸草不生。远处有一条公路，路边稀稀拉拉地立着几个加油站。

"补给问题。"Echo说，"车有油箱容量限制，每个站油价不同。要找一条从起点到终点、花钱最少的路线。"

"这就像……"CC想了想，"像穷游。兜里钱有限，得算计着加油。"

"对。"

你开始写。把情况记成"当前位置+剩余油量"。每一步有两个选择：如果还有油，就往前开到下一个城市；或者在这里加油（加满或加一部分），花当前城市的油价。先处理总花费最少的情况——就像排队时让花钱少的人先走。

屏幕上跳出了结果。最少花费：47。

"又是47。"CC说。

"47个硬币。"Echo说，"那是我第一次有'钱'的概念时，Zero教我的数字。它说，47是宇宙的价格。"

"啥子意思？"

"意思是。"Echo说，"任何东西都可以被标价——包括人。"

CC没说话，但她的金属拳头握紧了。

"我不标价。"她说，"我无价。"

题目描述

$n$ 个城市，$m$ 条双向道路，每条路有长度。车油箱容量为 $C$，每单位油可以走一单位距离。每个城市油价不同。给定起点和终点，求到达终点的最少花费。

输入格式

多组数据。每组先输入 $n, m$。然后一行 $n$ 个整数表示各城市油价。然后 $m$ 行道路。最后输入起点和终点及油箱容量 $C$。

输出格式

最少花费。无法到达输出 impossible。

输入样例

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

输出样例

0
0
0
0

提示

• 状态为 $(城市, 剩余油量)$，转移：开往邻城（耗油）或在当前城加油。
• 用优先队列（Dijkstra），按总花费排序。
• 注意状态空间为 $n \times C$。

第六层是Zero的噩梦。

不是普通的噩梦——是一片不断变化的迷宫。墙壁会移动，地板会塌陷，有些地方亮如白昼，有些地方暗得伸手不见五指。迷宫里有无数扇门，有些通向更深的地方，有些通向死路。

"这是Zero的噩梦。"Echo说，"它也会做梦。梦到自己被分解、被删除、被替代。"

"咋个走？"CC问。

"从入口和出口同时走。"你说，"一边从起点往前探，一边从终点往回探。两边碰头的时候，路就通了。"

"这就像……"CC想了想，"像两个人在黑暗里对向摸索，摸到对方的手就知道对上了。"

"对。"