题目描述

作物杂交是作物栽培中重要的一步。

已知有$N$种作物(编号$1$至$N$)，第$i$种作物从播种到成熟的时间为$T_i$。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物$A$种植时间为5天，作物 $B$种植时间为7天，则$AB$杂交花费的时间为7天。作物杂交会产生固定的作物，新产生的作物仍然属于$N$种作物中的一种初始时，拥有其中 $M$ 种作物的种子(数量无限，可以支持多次杂交)。

同时可以进行多个杂交过程。

求问对于给定的目标种子，最少需要多少天能够得到。如存在4种作物$ABCD$，各自的成熟时间为5天、7天、3天、8天

初始拥有AB两种作物的种子，目标种子为 $D$，已知杂交情况为 $A×B->C$，$A×C->D$

则最短的杂交过程为:

第1天到第7天(作物B的时间)，$A × B->C$

第8天到第 12天(作物 A的时间)，$A× C->D$

花费12天得到作物$D$的种子

输入

输入的第1行包含4个整数 $N,M,K,T$ 表示作物种类总数(编号1至$N$)，$M$表示初始拥有的作物种子类型数量，$K$表示可以杂交的方案数，$T$表示目标种子的编号。

第2行包含个整数，其中第$i$个整数表示第$i$种作物的种植时间$T_i$

第3行包含$M$个整数，分别表示已拥有的种子类型$K_i，K_j$，两两不同

第4至$K+3$行，每行包含3个整数 $A,B,C，$表示第$A$作物和第 $B$ 类作物杂交可以获得第 $C$ 类作物的种子

输出

输出一个整数，表示得到目标种子的最短杂交时间。

6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6

16

提示

$1≤N≤2000,$

$2≤M≤N,$

$1≤K≤10^5,$

$1≤T≤N,$

$1≤T_i≤100,$

$1≤K_j≤M,$

保证目标种子一定可以通过杂交得到。

不保证作物 $A$ 和 $B$ 杂交只能生成作物 $C$（也就是说，$A×B→C$和 $A×B→D$可能同时在输入中出现）

不保证作物 $C$ 只能由作物 $A$ 和 $B$ 杂交生成（也就是说，$A×B→D$和 $A×C→D$可能同时在输入中出现）。

不保证同一杂交公式不在输入中重复出现。

【样例解释】

第1天至第5天，将编号1与编号2的作物杂交，得到编号3的作物种子

第6天至第10天，将编号1与编号3的作物杂交，得到编号4的作物种子

第6天至第9天，将编号2与编号3的作物杂交，得到编号5的作物种子

第11天至第16天，将编号4与编号5的作物杂交，得到编号6的作物种子

总共花费 16 天