Milking Order (Bronze)#10382
Farmer John's cows, conveniently numbered as always, happen to have too much time on their hooves. As a result, they have worked out a complex social structure related to the order in which Farmer John milks them every morning. After weeks of study, Farmer John has discovered that this structure is based on two key properties.
First, due to the cows' social hierarchy, some cows insist on being milked before other cows, depending on their social status. For example, if cow has the highest status, cow has average status, and cow has low status, then cow must be milked before cow , and cow before cow .
Second, some cows allow themselves to be milked only at a certain position in the order. For example, cow might insist on being milked second.
Fortunately, Farmer John can always milk his cows in an order that satisfies all of these conditions.
Unfortunately, cow has recently fallen ill, so Farmer John wants to milk her as early as possible, so that she can return to the barn and get some much-needed rest. Help Farmer John determine the earliest position that cow can occupy in the milking order.
The first line contains three integers , , and k~(2 \le n \le 100, 1 \le m < n, 1 \le k < n): Farmer John has cows, of them form a social hierarchy, and of them demand to be milked at specific positions in the order. The second line contains distinct integers m_i~(1 \le m_i \le n); the cows listed in this line must be milked in the same order in which they appear. Each of the next lines contains two integers c_i and p_i~(1 \le c_i, p_i \le n), meaning that cow c_i must be milked at position p_i.
It is guaranteed that a valid milking order exists under these constraints.
Print one integer — the earliest position that cow can occupy in the milking order.
Example 1
In this example, Farmer John has cows, and cow is sick. He must milk cow before cow , and cow before cow . Moreover, cow must be milked first, and cow third.
Since cow is milked first and cow must come before cow , which is milked third, cow must be milked second. Thus, the earliest position for cow is the fourth.