Snow Chaos

A snowstorm has moved in and traffic is in chaos. On top of that, parts of the railway track are snowed over, which has stopped all train traffic. This is of course not good, since crowds of travelers are now stuck at their stations with no way to get anywhere. Fredrika has therefore been tasked with clearing the snow between the stations before rush hour begins and the disaster is a fact.

The railway track has no branches at all and has $n$ stations, numbered from $1$ to $n$ in the order they appear on the track (so station $i$ comes just before station $i+1$). There are thus $n - 1$ stretches between the stations. Of these, $s$ are covered in snow.

Fredrika is a little worried, because she has worked out that she only has time to clear the snow from $p$ stretches. To make the best of the situation, Fredrika decides to choose the stretches that let as many as possible of the waiting travelers get where they want to go. To help her, she has the answers from a survey she sent to everyone who is waiting, in which they answered which stations they want to travel between.

Assuming Fredrika chooses the stretches optimally, calculate how many waiting travelers will be able to travel once she is done.

Note that trains can only run on stretches without snow. Every station has trains parked at it, so every stretch without snow will be able to carry traffic, even if the stations cannot be reached from the endpoints of the track. Train traffic is completely stopped until Fredrika is done, so travelers who had a snow-free route from the start are also counted in the answer.

Figure 1: Sample 1

The first line contains four integers, $2 \le n \le 200$, $1 \le m \le 100000$, $0 \le s, p \le n - 1$: the number of stations, the number of travelers, the number of snowed-over stretches, and the number of stretches Fredrika has time to plow.

Then follow $m$ lines, where line $i$ contains two integers $1 \le a_i \not= b_i \le n$, the stations where traveler $i$ wants to start and end.

Then follow $s$ lines, where line $j$ contains an integer $1 \le c_j \le n - 1$, the station that lies just before snowed-over stretch $j$. A stretch appears at most once in this list.

Your program should print a single integer: the largest number of travelers who can complete their journeys by plowing at most $p$ stretches.