폭설 대란

눈보라가 몰아쳐 교통이 마비되었다. 설상가상으로 철로의 일부 구간이 눈에 파묻혀 모든 열차 운행이 중단되었다. 수많은 승객이 각자의 역에서 발이 묶여 아무 데도 갈 수 없게 되었으므로, 이는 당연히 좋지 않은 상황이다. 따라서 Fredrika는 출퇴근 시간이 시작되어 재앙이 현실이 되기 전에 역 사이의 눈을 치우는 임무를 맡았다.

철로에는 분기점이 전혀 없으며, $n$개의 역이 철로에 나타나는 순서대로 $1$부터 $n$까지 번호가 매겨져 있다(따라서 역 $i$은 역 $i+1$의 바로 앞에 있다). 따라서 역 사이에는 $n - 1$개의 구간이 있다. 이 중 $s$개가 눈으로 덮여 있다.

Fredrika는 자신이 $p$개 구간의 눈만 치울 수 있다고 계산했기 때문에 조금 걱정하고 있다. 상황을 최대한 개선하기 위해 Fredrika는 기다리는 승객 중 가능한 한 많은 사람이 원하는 곳으로 갈 수 있게 하는 구간들을 선택하기로 한다. 이를 위해 기다리는 모든 사람에게 보낸 설문 조사에서 어느 역 사이를 이동하고 싶은지 물어 얻은 답변을 활용한다.

Fredrika가 구간들을 최적으로 선택한다고 할 때, 작업이 끝난 뒤 이동할 수 있는 대기 승객의 수를 계산한다.

열차는 눈이 없는 구간에서만 운행할 수 있음에 유의한다. 모든 역에 열차가 주차되어 있으므로, 역들이 철로의 종착역에서 도달할 수 없는 곳에 있더라도 눈이 없는 모든 구간에서 열차를 운행할 수 있다. Fredrika가 작업을 마칠 때까지 열차 운행은 완전히 중단되므로, 처음부터 눈이 없는 이동 경로를 가진 승객도 답에 포함된다.

예제 1

점수 산정

제출한 풀이는 여러 테스트 케이스 그룹으로 채점된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 | 기타

1 | 12 |$n \le 200, m \le 100, p = 1$|

2 | 11 |$n \le 200, m \le 100, s \le 12$|

3 | 10 |$n \le 200, m \le 100$| 모든 $a_i$에 대해 $a_i = 1$

4 | 67 |$n \le 200$|

첫째 줄에는 네 정수 $2 \le n \le 200$, $1 \le m \le 100000$, $0 \le s, p \le n - 1$이 주어진다. 각각 역의 수, 승객의 수, 눈에 파묻힌 구간의 수, Fredrika가 제설할 수 있는 구간의 수이다.

이후 $m$개의 줄이 주어지며, $i$번째 줄에는 승객 $i$이 각각 출발하고 도착하려는 역을 나타내는 두 정수 $1 \le a_i \not= b_i \le n$이 주어진다.

이후 $s$개의 줄이 주어지며, $j$번째 줄에는 눈에 파묻힌 구간 $j$의 바로 앞에 있는 역을 나타내는 정수 $1 \le c_j \le n - 1$이 주어진다. 하나의 구간은 이 목록에 최대 한 번만 등장한다.

최대 $p$개의 구간을 제설하여 이동을 완료할 수 있는 승객 수의 최댓값을 하나의 정수로 출력한다.