HZNUOJ

宝物

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:7     AC:6     Score:99.66

Description

传说 HMH 大沙漠中有一个迷宫,里面藏有许多宝物。迷宫里可能有 N 个藏宝地点,用 1 到 N标记。藏宝地点之间最多有一条通路相连。标记 1 为迷宫的进出口。

某天,Dr.Kong 找到了迷宫的地图,他已经知道其中 K(1<=K<=N)个不同的地点真的藏有宝物。Dr.Kong 决定让他的机器人卡多去探险。卡多在经过某个藏宝地点时可能会拿走宝物。但它每拿走一个藏宝地点的宝物后,它的载重量就会增加 W。迷宫中的通路不是平坦的,到处都是陷阱。假设每条通路都有一个危险度,其值与通过此路的载重量成正比。

当机器人卡多进入迷宫时,它的载重量为 0。只有当卡多携带宝物的载重量不大于某个通路的危险度时,它才能顺利通过此条道路,否则就会掉入陷阱,不能出来。

Dr.Kong 希望他的机器人卡多尽量多的带出宝物,当然他更希望卡多最后能从标记 1 的地点走出去。

请你编写程序,帮助 Dr.Kong 计算一下,卡多最多能带出多少个藏宝地点的宝物。

Input

第 1 行: N M K W(1 ≤ N ≤ 8000 1 ≤ K ≤ N 1 ≤ M ≤ 15000 1 ≤ W, Z ≤ 10000,数 据保证所有的地点之间都是有道路可以到达的 )

接下来有 K 行, 每行一个整数,表示藏有宝物的地点标号。

再接下来有 M 行,每行三个整数 X,Y,Z,表示地点 X 与地点 Y 之间有一条危险度为 Z 的通路。

Output

输出有 一个整数, 表示卡多最多能带出的宝物的堆数。

Samples

input
6 7 5 1 1 2 3 4 5 1 2 3 3 6 2 6 2 10 2 4 1 5 1 1 4 5 1 1 6 1
output
4

Hint

机器人卡多经过一个藏宝地点时可以不拿走宝物, 而且同一个藏宝地点可以经过多次。

Source

第四届河南省大学生程序设计竞赛