热心群友豆猫所在的城市有着编号为1到$N$的机场。第$i$个机场的海拔是$H_i$米。

飞行员豆猫君能在其中的$M$对机场之间直接飞行，在各对机场之间飞行所需的时间是固定的。

当豆猫在机场之间飞行的时候，他离地面的高度每秒会下降1米。

也就是说，如果豆猫现在离地高度是$h$米，在机场之间飞行需要$t$秒，那么飞行之后的离地高度就会变成$h-t$米。

规定：当$h-t$小于0或大于目标机场的高度时则不能飞行。

豆猫君还能沿着他所在的机场上下移动(对，他开的是直升机），使得他的离地高度在0到当前所在机场高度的范围内变化。

飞行员豆猫每次使自己的离地高度增加或减少1米都需要1秒的时间。

现在，豆猫要从1号机场上高度为$X$米的位置出发，到机场$N$的顶端（高度为米$H_N$的位置）去。

他想知道为了达成这个目标所需时间的最小值。

由于豆猫去机场上班了，这个任务就交给热爱编程的你了。

一句话题目：给出各个机场的高度，飞行员豆猫能直接飞行的机场对和豆猫君最初所在位置的高度，请求出到达机场$N$顶端所需时间的最小值。

输入格式

第一行包含三个整数$N,M,X$

接下来$N$行中，第$i$行有一个整数，表示机场$i$的高度是$H_i$米。

接下来$M$行中，第$j$行有三个整数$A_j,B_j,T_j$，表示豆猫能花$T_j$秒的时间从$A_j$飞到$B_j$或从$B_j$飞到$A_j$。

输出格式

仅一行一个整数，所需时间的最小值（单位：秒）

如果不能到达目的地则输出-1

输入样例1

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

输出样例1

110

输入样例2

2 1 0
1
1
1 2 100

输出样例2

-1

数据范围与提示

样例1解释：（不唯一）

沿着机场1向上飞50米

从机场1飞到机场2

从机场2飞到机场4

从机场4飞到机场5

沿着机场5向上飞10米

样例2解释：adou无法从机场1飞到机场2

对于100%的数据，满足：

$2<=N<=10^5$

$1<=M<=10^6$

$1<=H_i<=10^9（1<=i<=N）$

$1<=T_j<=10^9（1<=j<=M）$

$0<=X<=H_1$

对于前25%的数据，满足

$2<=N<=1000$

$1<=M<=3000$

$1<=H_i<=100（1<=i<=N）$

$1<=T_j<=100（1<=j<=M）$

对于中间25%的数据，满足$X=0$

对于剩下的50%数据，一切精彩尽在其中。