Concerto de Pandemic

도시는 1번부터 $N$번까지 번호가 붙은 $N$개가 있다. $1 \le i < N$인 모든 $i$에 대해 도시 $i$와 도시 $i + 1$을 잇는 양방향 도로가 있고, 도시 $N$과 도시 $1$도 도로로 연결되어 있다. 도로 하나를 지나는 데 1일이 걸린다.

전염병 때문에 $M$개의 도시는 방문자에게 격리 명령을 내린다. 도시 $C_i$를 방문한 사람은 그 도시의 정부 시설에서 정확히 $T_i$일 동안 격리된다. 이 명령은 그 도시에 머물 생각이 없고 단순히 지나가기만 하는 사람을 포함한 모든 방문자에게 적용된다.

Nawan은 열성 팬 $K$명을 둔 떠오르는 젊은 음악가다. $i$번째 팬은 도시 $D_i$에 산다. 놀랍게도 격리 명령이 있는 도시에 사는 팬은 없다.

Nawan은 새 앨범을 냈고 팬들을 위해 콘서트를 열고 싶어 한다. 팀의 반대에도 Nawan은 콘서트를 온라인이 아니라 직접 현장에서 열어야 한다고 고집한다. 가상 콘서트로는 자신의 음악적 감성을 전할 수 없다고 믿기 때문이다.

예산과 자원을 따져 본 뒤 Nawan과 팀은 콘서트를 최대 $P$회까지 여는 데 합의한다. 콘서트는 격리 명령이 없는 도시에서만 열 수 있다. Nawan은 모든 팬에게 연락했고, 각 팬은 콘서트 한 곳에만 참석하기로 동의했다. 남은 문제는 어느 도시에서 콘서트를 열지 고르는 것이다. 각 팬은 이동 시간이 가장 짧은 공연장으로 간다. 공연장의 수용 인원에는 제한이 없다.

Nawan은 최대 $P$개의 도시에서 콘서트를 열되, 모든 팬 가운데 가장 긴 이동 시간이 가능한 한 작아지기를 원한다. 출력해야 할 것은 그 최솟값뿐이다.

첫 줄에 정수 $N$, $M$, $K$, $P$가 주어진다($1 \le M < N \le 200000$, $1 \le K, P \le N - M$). 각각 도시의 수, 격리 명령을 내린 도시의 수, 팬의 수, 열 수 있는 콘서트의 최대 횟수다. 다음 $M$개의 줄에는 정수 $C_i$와 $T_i$가 주어진다($1 \le C_i \le N$, $1 \le T_i \le 200000$). 모든 $C_i$는 서로 다르다. 마지막 줄에는 $K$개의 정수 $D_i$($1 \le D_i \le N$)가 주어지며, 이는 각 팬이 사는 도시다. 팬이 사는 도시는 격리 명령이 있는 도시가 아니고, 모든 팬은 서로 다른 도시에 산다.

가장 긴 이동 시간의 최솟값을 한 줄에 정수로 출력한다. 이동 시간은 팬들이 콘서트 공연장에 도착하기까지 걸리는 시간 중 가장 긴 값을 말한다.