泡泡杯X的参赛者们在赛后聚集在一起,讨论什么是了解主办国及其城市的最佳方式。
经过对塞尔维亚地图一段时间的探索,参赛者们得出了以下事实:该国有 V 个城市,分别用 1 到 V 的数字进行索引,并且有 E 条双向道路连接这些城市。每条路都有一个权重(穿过该路所需的时间)。泡沫杯比赛共有 N 支队伍,参赛者们制定了如下计划:N 支队伍各在 V 个城市之一开始旅程,部分队伍共享起始位置。
他们想要找到最短的时间T,使得每个团队都可以在这T分钟内移动,并且他们最终到达的不同城市的数量至少为K(因为他们只会知道他们最终到达的城市)。团队不必一直在移动,如果他们喜欢某个特定的城市,他们可以呆在那里等待时间过去。
请帮助参赛者确定最短时间T,以便他们有可能最终到达至少K个不同的城市,如果无论他们如何移动都不可能,则打印-1。
请注意,某些城市之间可能存在多条道路。
输入
第一行包含四个整数:V、E、N 和 K(1 ≤ V ≤ 600、1 ≤ E ≤ 20000、1 ≤ N ≤ min(V, 200)、1 ≤ K ≤ N)、城市数量、道路数量、团队数量以及最终需要到达的不同城市的最小数量。
第二行包含N个整数,即队伍开始旅程的城市。
接下来的 E 行包含以下格式的道路信息:Ai Bi Ti (1 ≤ Ai, Bi ≤ V, 1 ≤ Ti ≤ 10000),这意味着有一条道路连接城市 Ai 和 Bi,穿过该道路需要 Ti 分钟。
输出
输出一个整数,表示团队可以移动的最短时间,这样他们最终会到达至少 K 个不同的城市,如果没有解决方案,则输出 -1。
如果解存在,结果将不大于 1731311。
示例
输入 #1
6 7 5 4 5 5 2 2 5 1 3 3 1 5 2 1 6 5 2 5 4 2 6 7 3 4 11 3 5 3
输出 #1
3
注意
三支队伍从城市 5 出发,两支队伍从城市 2 出发。如果他们同意移动 3 分钟,一种可能的情况是:城市 2 两支队伍,城市 5 一支队伍,城市 3 一支队伍,城市 1 一支队伍。我们看到队伍在四个不同的城市结束旅程。