题目描述

作物杂交是作物栽培中重要的一步。已知有 $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$，$N$ 表示作物种类总数 (编号 1 至 $N$)，$M$ 表示初始拥有的作物种子类型数量，$K$ 表示可以杂交的方案数，$T$ 表示目标种子的编号。

第 $2$ 行包含 $N$ 个整数，其中第 $i$ 个整数表示第 $i$ 种作物的种植时间 $T_i (1≤T_i≤100)$。

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

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

其中，$1≤N≤2000,2≤M≤N,1≤K≤10^5,1≤T≤N$, 保证目标种子一定可以通过杂交得到。

输出描述

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

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$ 天至第 $5$ 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。

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

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

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

总共花费 $16$ 天。

评测用例规模与约定：

对于所有评测用例，$1 \leq n \leq 2000，2 \leq M \leq N，1 \leq K \leq 100000，1 \leq T \leq N$，保证目标种子一定可以通过杂交得到。

额外提示

从数据规模可以看出，很显然，同一种种子的获取方法不止一种。