Thỏ ăn cỏ

Bối cảnh

Hiếu có \(N\) con thỏ \((2≤N≤100)\), được đánh số từ \(1\) đến \(N\). Hiếu nhận thấy thỏ có thời gian rảnh rỗi quá nhiều nên chúng đã thiết lập một hệ thống phân cấp xã hội phức tạp, quy định thứ tự ăn cỏ vào mỗi bữa ăn. Sau nhiều tuần quan sát, Hiếu đã khám phá ra rằng cấu trúc xã hội này dựa trên hai đặc điểm chính:

Yêu cầu

• Thứ nhất: Do tôn ti trật tự trong xã hội của đàn thỏ, một số con nhất quyết đòi được ăn cỏ trước những con khác, dựa trên địa vị xã hội. Ví dụ, nếu con thỏ số \(3\) có địa vị cao nhất, con thỏ số \(2\) có địa vị trung bình và con thỏ số \(5\) có địa vị thấp, thì con thỏ số \(3\) cần được ăn cỏ sớm nhất, tiếp theo là con thỏ số \(2\), và cuối cùng là con thỏ số \(5\).
• Thứ hai: Một số con thỏ khăng khăng chỉ cho phép mình được ăn cỏ ở một vị trí nhất định trong thứ tự. Ví dụ, con thỏ số \(4\) có thể nhất quyết đòi được ăn cỏ ở vị trí thứ hai trong toàn bộ thứ tự ăn cỏ.

May mắn thay, Hiếu luôn có thể cho thỏ ăn cỏ theo thứ tự thỏa mãn tất cả các điều kiện này.

Nhưng không may, con thỏ số \(1\) gần đây đã bị ốm. Hiếu muốn cho con thỏ bị bệnh này ăn cỏ càng sớm càng tốt trong thứ tự, để nó có thể quay trở lại chuồng và nghỉ ngơi. Xin hãy giúp Hiếu xác định vị trí sớm nhất mà con thỏ số \(1\) có thể xuất hiện trong thứ tự ăn cỏ.

Input

Dòng đầu tiên gồm ba số \(N, M (1≤M<N),\) và \(K (1≤K<N)\), cho biết Hiếu có \(N\) con thỏ, \(M\) con trong số đó đã tự sắp xếp thành một hệ thống phân cấp xã hội, và \(K\) con thỏ yêu cầu được ăn cỏ ở một vị trí cụ thể.

Dòng tiếp theo chứa \(M\) số nguyên khác nhau \(m_i (1≤m_i≤N)\). Thỏ trên dòng này phải được ăn cỏ đúng theo thứ tự xuất hiện.

\(K\) dòng tiếp theo chứa hai số nguyên \(c_i (1≤c_i≤N)\) và \(p_i (1≤p_i≤N)\), cho biết con thỏ \(c_i\) phải được ăn cỏ ở vị trí \(p_i\).

Đảm bảo rằng Hiếu sẽ có thể xây dựng được một thứ tự ăn cỏ hợp lệ.

Output

Vui lòng cho biết vị trí sớm nhất mà con thỏ số 1 có thể được ăn.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

6 3 2
4 5 6
5 3
3 1

Output

4

Giải thích ví dụ

Giải thích: Trong ví dụ này, Hiếu có sáu con thỏ, trong đó con thỏ số \(1\) bị bệnh. Anh ta cần cho con thỏ số 4 ăn trước con thỏ số 5, và con thỏ số 5 trước con thỏ số 6. Hơn nữa, Hiếu phải cho con thỏ số 3 ăn trước tiên và con thỏ số 5 ở vị trí thứ ba. Vì con thỏ số 4 phải đứng trước con thỏ số 5 nên con thỏ số 4 phải được ăn ở vị trí thứ hai, và con thỏ số 5 thứ ba. Do đó, con thỏ số 1 có thể đứng sớm nhất ở vị trí thứ tư.

Thông tin học tập

• Buổi: B10
• Concepts: 1D arrays, fixed positions, ordering simulation
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 40