Порядок доения (Бронза)
n коров Фермера Джона, последовательно пронумерованных 1..n разработали структуру утреннего доения. Она основывается на двух ключевых свойствах:
Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет средний статус, а корова 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.