说明

Once upon a time there was a city, There are $n$ wastewater treatment plants in the city, They are connected to each other by $m$ pipes. For each pipe $i$, There are three parameters $u,v,w$ express $u \rightarrow v$ or $v \rightarrow u$ 's maximum flow volume is $w$ tons.

However, the treatment capacity of each wastewater treatment plant is also limited, the $i_{th}$ treatment plant can only process $a_i$ ton of wastewater per second.

In particular, the waste water treatment plant which marked $S$ is actually a waste water discharge plant. Means that $a_S$ ton of water flows out per second (only out and not in). The waste water treatment plant marked $T$ is actually a collection site. Means that $a_T$ ton of treated water can be collected per second (only in but not out).

Can you tell me how long will it take at least for the collection site to collect $Q$ tons of treated water (as long as it passes through a wastewater treatment plant, it is treated).

Assume that it does not take time to flow in the pipeline. The time is in integer seconds. For example, if you need $2.3$s to collect, you need to output $3$s.

输入格式

The first line contains two integers $n$ and $m$ $(3\leq n\leq200, 1\leq m \leq1000)$, represent the number of wastewater treatment plants and the number of pipes.

The second line contains $n$ integers, indicating that the $i_{th}$ treatment plant can process $a_i$ $(1\leq a_i \leq 10^6)$ tons of wastewater per second.

The next $m$ lines, each line contains three integers $u, v, w$ $(1\leq u,v\leq n,1\leq w\leq10^6)$ representing the treatment plant connected by the pipeline and the maximum flow rate of the pipeline, ensuring that there is no multiple edges, no self-loop, and the graph is connected.

The last line contains three integers $S, T, Q$ $(1\leq S, T \leq n, 1 \leq Q \leq 10^9)$, which represent the discharge plant number, collection site number and the amount of water that needs to be collected in the collection site.

输出格式

Output minimum number of seconds.

样例

4 5
3 2 1 4
1 2 2
2 4 6
1 3 7
3 4 4
1 4 3
4 1 28 

5