정밀지도 제작

문제

현대오토에버는 미래차 성장 동력의 한 축인 인포테인먼트 산업 전반을 혁신적으로 리드합니다. GIS 분야의 축적된 기술력과 노하우를 바탕으로 디지털 맵, 내비게이션 SW, 자율주행 정밀 지도를 정교하게 제작하고 글로벌 위치 기반 콘텐츠와 통합 OTA 서비스를 제공하여 사용자가 전혀 다른 모빌리티 서비스, 혁신적인 카 라이프를 경험할 수 있도록 합니다.

현대자동차그룹이 레벨3 자율주행차 상용화 목표에 발맞춰 총력을 다하고 있는 가운데, 국내 최고 수준의 지도 구축 기술력을 보유한 현대오토에버는 자율주행에 필요한 정밀지도를 제작해 배포하고, 기술 고도화를 위한 연구에 매진하고 있습니다. 카메라와 센서만으로는 탑재 장치에 이상이 생기거나 눈, 짙은 안개 등 기상 상황이 악화되었을 때 주변 상황을 제대로 인지할 수 없기 때문입니다. 정밀지도에는 도로의 경계와 차선은 물론 각종 시설물의 정보가 cm 단위로 매우 상세하게 표시됩니다. 또한 중앙선과 경계선 등 차선 단위 정보와 신호등, 횡단보도, 표지판, 노면 마크 등을 3D로 확보해 악천후나 차량 센서 고장처럼 긴급 상황에서도 자율주행차가 안정적으로 주행할 수 있도록 도와줍니다.

현대오토에버에서 근무하는 종서는 도로 데이터를 기반으로 자동으로 정밀지도를 구축하는 지도 자동 구축(Map Auto Creation) 기술을 개발해 지도 제작 시간을 단축하고 정밀도를 향상시키는 연구를 진행 중이다. 종서는 MAC 기술을 이번에 새로 지어지는 신도시에 적용하기로 결정했다.

종서가 분석하고 있는 신도시에는 $1$ 번부터 $N$ 번까지 번호가 붙여진 $N$ 개의 교차로가 있다. 앞으로 신도시에는 서로 다른 두 교차로를 잇는 도로가 $M$ 개 지어질 것이다. 신도시는 교차점을 정점으로, 도로를 간선으로 하는 단순 연결 그래프 형태이다.

도로는 각각 $1$ 번부터 $M$ 번까지 번호가 붙여져 있다. $i$ 번 도로는 $a\_i$ 번 교차로와 $b\_i$ 번 교차로를 이으며, $k\_i$ 시점에 건설이 완료될 예정이다. 종서는 적당한 음이 아닌 정수 $t$ 를 정한 뒤에, 각 도로마다 건설된 직후부터 $t+0.5$ 만큼의 시간 동안 도로를 분석하여 정밀지도를 제작할 예정이다. 따라서 $i$ 번 도로는 정확히 $\[k\_i,k\_i+t+0.5)$ 구간에서 분석될 예정이다.

교차로 중 $P$ 개의 교차로 $s\_1,s\_2,\dots ,s\_P$ 에는 건물이 지어져 있다. 이번 정밀지도 구축의 핵심 목적 중 하나는, 이 건물들 사이에서 자율주행차량의 원활한 이동이 가능한지를 확인하는 것이다.

종서는 서로 다른 $Q$ 개의 시각 $T\_1,T\_2,\dots ,T\_Q$ 를 잘 정해서, 서로 다른 $Q$ 개의 지도 데이터를 확보하고자 한다. 만약 시각 $T\_i$ 에 분석 중인 도로들만으로 모든 임의의 두 건물 사이를 이동할 수 있다면 종서는 지도 데이터 $i$ 를 얻는다. 두 지도 데이터 $i$ 와 $j$ 가 다르다는 것은, 시각 $T\_i$ 에 분석 중인 도로들의 집합이 시각 $T\_j$ 에 분석 중인 도로들의 집합과 다름을 의미한다.

종서는 분석 비용을 절감하기 위해 $t$ 를 최소화하고 싶다. 서로 다른 $Q$ 개의 지도 데이터를 확보 가능한 최소 $t$ 는 얼마인가?

입력

첫째 줄에 $N,M,P,Q$ 가 공백을 구분으로 주어진다.

다음 줄에 건물이 있는 교차로의 번호 $s\_i$ 가 공백을 구분으로 주어진다.

이후 $M$ 개의 줄에는 $i$ 번째 줄에 $i$ 번 도로에 대한 정보인 $a\_i, b\_i, k\_i$ 가 주어진다.

출력

조건을 만족하는 최소 $t$ 을 출력한다. 만약 조건을 만족할 수 없다면 -1을 출력한다.

제한

$2\le N\le 100\\, 000$
$1\le M\le 300\\, 000$
$2 \le P \le N$
$1\le a\_i,b\_i,s\_i \le N$
$1\le k\_i \le 10^{9}$
$1\le Q \le 10^{6}$
$k\_i$ 는 모두 다르다.
$s\_i$ 는 모두 다르다.
신도시를 그래프로 나타내면, 단순 연결 그래프이다.