题目背景

亮亮学长：“这对局，分明是老叟戏顽童，我们一点赢的概率都没有……”

起因是亮亮、小玫两位学长和一个神秘人CS2自建房对掏，经过一阵对掏，两人惨遭零封。

于是两个学长使用出“终极武器”：钵钵鸡学长，古希腊掌管偷背身的神，让人不敢立定架狙5秒的存在。

现在他们请你帮忙规划一下偷背身的路线。

说明

CS的地图可以抽象成一张图，有 $n$ 个节点， $e$ 号节点是神秘人与亮亮小玫架狙对枪的地方。

然额自建房里有人机，所以钵钵鸡想要偷到背身还需清理一路上的所有人机，因为是偷背身，所以清理的人机越少越好。

因为技术天堑，亮亮和小玫两位学长能拖住的时间有限，请你在 $1s$ 内算出钵钵鸡从家(也就是 $1$ 号节点)到神秘人所在地(也就是 $e$ 号节点)路途中最少要清理的人机数。

第一行三个整数 $n,m,e$ ，表示共 $n$ 个节点， $m$ 条边，神秘人在 $e$ 号节点。

第二行 $n$ 个整数，第 $i$ 个整数表示该编号节点上的人机个数。

接下来 $m$ 行，每行两个整数 $u,v$ 代表有一条有向边从 $u$ 指向 $v$ 。

一个整数，表示钵钵鸡最少要清理的人机数。

$1\le n\le 500,1\le m\le 10^4$
对于前 $40\%$ 的数据 $e=n$ ，所有路径上节点编号从小到大
保证人机总数不超过 $10^9$ ，且不存在任何人机数量小于 $0$ 的节点。
保证给的图没有重边和自环，保证一定有一条从 $1$ 号节点到 $n$ 号节点的路径。