题目背景

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

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

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

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

说明

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

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

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

输入格式

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

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

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

输出格式

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

样例

5 6 5
0 2 6 3 0
1 2
3 4
4 5
2 3
1 3
2 4

5

数据范围

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