Порядок доїння (Бронза)
n корів Фермера Джона, пронумерованих від 1 до n, розробили порядок ранкового доїння, який базується на двох основних правилах:
Деякі корови вимагають, щоб їх доїли раніше за інших, відповідно до їх соціального статусу. Наприклад, якщо корова 3 має найвищий статус, корова 2 - середній, а корова 5 - найнижчий, то корову 3 потрібно доїти першою, потім корову 2, а потім корову 5.
Деякі корови наполягають, щоб їх доїли на певній позиції в черзі. Наприклад, корова 4 може вимагати, щоб її доїли другою серед усіх корів.
На щастя, Фермер Джон завжди може організувати доїння так, щоб задовольнити всі ці умови.
Однак, корова 1 захворіла, тому Фермер Джон хоче подоїти її якомога раніше, щоб вона могла швидше повернутися до амбару для відпочинку та одужання. Допоможіть Фермеру Джону визначити найранішу позицію, на якій можна подоїти корову 1.
Вхідні дані
Перший рядок містить n (2 ≤ n ≤ 100), m (1 ≤ m < n), k (1 ≤ k < n), що означає, що у Фермера Джона n корів, m з яких мають соціальну ієрархію, а k вимагають, щоб їх подоїли на певній позиції. Наступний рядок містить m різних цілих чисел m[i] (1 ≤ m[i] ≤ n). Корови, зазначені в цьому рядку, повинні бути подоєні в порядку, в якому вони з'являються в цьому рядку. Наступні k рядків містять по два цілі числа c[i] (1 ≤ c[i] ≤ n) і p[i] (1 ≤ p[i] ≤ n), що вказують, що корова c[i] повинна бути подоєна на позиції p[i].
Гарантується, що Фермер Джон може скласти порядок доїння, який задовольняє всім умовам.
Вихідні дані
Виведіть найранішу позицію, на якій можна подоїти корову 1.
Приклад
У цьому прикладі у Фермера Джона 6 корів. Він повинен спочатку подоїти корову 4, потім корову 5, потім корову 6. Крім того, він повинен подоїти корову 3 першою, а корову 5 третьою.
Фермер Джон повинен подоїти корову 3 першою, а корову 5 - третьою. Оскільки корову 4 потрібно подоїти перед коровою 5, виходить, що її потрібно подоїти другою. Тому найраніше, коли можна подоїти корову 1 - позиція 4.