题目背景

Han24666 玩三角洲破产了,他得回到普坝抢保险赚钱

题目描述

三角洲的零号大坝可以抽象为一个 $n$ 个点, $m$ 条单向边的图,保证图是强连通图,每条边有 $3$ 个信息,起点 $u$,终点 $v$,走过要花费的时间 $w$,每一局会刷新 $t$ 个大保险箱,第 $i$ 个保险箱的位置为 $a_i$ ,其中大保险的价值从大到小(位置为 $a_1$ 的最大, $a_t$最小), Han24666的眼中,他必须严格按照从 $1-t$ 的顺序抢保险,问他从出生点 $s$ 到 $a_1$ 到 $a_2$ 一直到 $a_t$ 再到撤离点 $f$ 的时间为多少, 但是如果这个时间超过了 $k$(游戏限制一局时间,超过会撤离失败),请输出他最多能抢到多少个保险(Han24666十分贪财，就算抢完了保险剩余时间不够到撤离点他也要抢这个保险，例如 $k=5$，抢完$1$号保险的时间恰好为 $5$,但从 1 号保险到撤离点需要 1 时间,这时输出 $1$ 而不是 $0$)

输入格式

第一行 $6$ 个整数:$n,m,t,s,f,k$

第二行 $t$ 个整数, 第 $i$ 个数表示 $a_i$

接下来 $m$ 行, 每行 $3$ 个整数 $u,v,w$ 表示一条边的信息

输出格式

如果可以在 $k$ 时间内到达撤离点,请输出具体时间

否则输出最多可以抢到的保险数量

样例输入

5 5 3 1 5 100
1 3 5
1 2 1
2 3 1
3 4 1
4 5 1
5 1 1

样例输出

4

数据规模与约定

$a_i,w \le10^5$

$s,f,k,u,v \le n$