Problem Description

Farmer John’s $N$ cows ($2\le N\le 100$), conveniently numbered $1\ldots N$, have been feeling bored. So, they have developed a complex social structure related to the order they line up in each morning when Farmer John milks them. After several weeks of study, Farmer John has found that this structure is based on two key properties.

First, because of the cows’ social ranks, some cows insist on being milked before other cows, based on their rank. For example, if cow $3$ has the highest rank, cow $2$ is in the middle, and cow $5$ is low-ranked, then cow $3$ must be milked first, then cow $2$, and finally cow $5$.

Second, some cows will only allow themselves to be milked at a specific position in the line. For example, cow $4$ might insist on being the second cow to be milked out of all the cows.

Fortunately, Farmer John can always milk his cows in an order that satisfies all of these conditions.

Unfortunately, cow $1$ has recently become sick, so Farmer John wants to milk her as early as possible, so she can return to the barn for some much-needed rest. Please help Farmer John determine the earliest possible position where cow $1$ can appear in the milking order.

Input Format

The first line contains $N$, $M$ ($1\le M<N$), and $K$ ($1\le K<N$), meaning Farmer John has $N$ cows, of which $M$ form a social hierarchy, and $K$ must be in specific positions in the milking order. The next line contains $M$ distinct integers $m_i$ ($1\le m_i\le N$). The cows listed on this line must be milked in the same relative order as they appear in this line. The following $K$ lines each contain two integers $c_i$ ($1\le c_i\le N$) and $p_i$ ($1\le p_i\le N$), meaning cow $c_i$ must be milked in position $p_i$.

The input guarantees that under these constraints, Farmer John can construct a milking order that satisfies all requirements.

Output Format

Output the earliest possible position where cow $1$ can appear in the milking order.

6 3 2
4 5 6
5 3
3 1

4

Hint

In this example, Farmer John has six cows, and cow $1$ is sick. His milking order must have cow $4$ before cow $5$, and cow $5$ before cow $6$. Also, Farmer John must milk cow $3$ first, and cow $5$ third.

Since FJ must milk cow $3$ first, and because cow $4$ must be before cow $5$, cow $4$ has to be milked second, and then cow $5$ third. Therefore, the earliest possible position for cow $1$ in the milking order is fourth.

Translated by ChatGPT 5