Yuki is a geeked girl and she is an administrator of SUSTech Open Source Mirrors.

There are totally \(n\) pieces of data stored in the open-source mirrors, with \(m\) storage servers. To ensure the availability of the mirrors, Yuki applies two-way replication, that is each piece of data is stored in two different servers completely and identically.

Unfortunately, according to the arrangement of the university’s information technology services center (ITS), each storage server needs maintenance periodically. To be specific, the maintenance period is \(t\) days, and the \(i\)-th server needs maintaining at day \(d_i,d_i+t,d_i+2t,\cdots (0\leq d_i < t) \). Notice that during the maintenance of the \(i\)-th server, data stored in this server cannot be obtained. Hopefully, ITS promises that each piece of data could be obtained during the maintenance (i.e. the two storage servers for each piece of data will not be maintained simultaneously).

However, due to some outbreak events, Yuki must postpone the maintenance time of one of the servers (let it be the \(k\)-th server) by exactly one day (i.e. the maintenance time for \(k\) is at day \(d_k+1,d_k+t+1,d_k+2t+1,\cdots\)). And in this case, Yuki maybe needs to postpone the maintenance time of some other storage servers by exactly one day to ensure that all pieces of data are still available during the maintenance.

Now Yuki wants to know which \(k\) she should choose, to minimize the total number of the storage servers whose maintenance time should be postponed by exactly one day. To make the problem easier, you only need to tell her this minimum number.

The first line contains three integers: \(n\), \(m\) and \(t\) \((1\leq n,m\leq 100\ 000,2\leq t\leq 100\ 000)\) — the number of pieces of data, the number of storage servers and the maintenance period.

Each of the next \(n\) lines contains two integers: \(u_i\) and \(v_i\) \((1\leq u_i,v_i\leq m)\), meaning that the \(i\)-th piece of data is stored in the \(u_i\)-th and \(v_i\)-th storage server completely and identically.

The last line contains \(m\) integers — the \(i\)-th integer indicates \(d_i\) \((0\leq d_i < t) \).

Print one line with an integer — the minimum number of the storage servers whose maintenance time needs postponing (including \(k\)-th server itself).

5 4 4
1 2
1 3
1 4
2 3
3 4
2 1 0 3

4