n коров Фермера Джона, последовательно пронумерованных 1..n разработали структуру утреннего доения. Она основывается на двух ключевых свойствах:

1. Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет средний статус, а корова 5 имеет низкий статус, то корову 3 нужно доить первой, затем корову 2 и затем корову 5.

2. Некоторые коровы могут настаивать, чтобы их доили в определённой позиции внутри порядка. Например, корова 4 может настаивать, чтобы её доили второй среди всех коров.

По счастью, ФД всегда может подоить своих коров в порядке, удовлетворяющем всем условиям.

К несчастью, корова 1 заболела, поэтому ФД хочет подоить эту корову как можно раньше, чтобы раньше отпустить её в амбар отдыхать и выздоравливать. Помогите ФД определить самую раннюю позицию, в которой можно будет подоить корову 1.

Входные данные

Первая строка содержит n (2 ≤ n ≤ 100), m (1 ≤ m < n), k (1 ≤ k < n), указывающая, что у ФД n коров, m из которых организованы в социальную иерархию, k из которых требуют, чтобы их подоили в определённой позиции порядка. Следующая строка содержит m различных целых чисел mi (1 ≤ mi ≤ n). Коровы, представленные в этой строке должны доиться в порядке, в котором они появились в этой строке. Следующие k строк содержат по по два целых числа ci (1 ≤ ci ≤ n) и pi (1 ≤ pi ≤ n), указывающих, что корова ci должна быть подоена на позиции pi.

Гарантируется, что ФД может сконструировать порядок доения, удовлетворяющий всем условиям.

Выходные данные

Выведите самую раннюю позицию, на которой можно подоить корову 1.

Пример

В этом примере у ФД 6 коров. Он должен сначала подоить корову 4,потом корову 5, потом корову 6. Кроме того, он должен подоить корову 3 первой, а корову 5 третьей.

ФД должен подоить корову 3 первой, а корову 5 - третьей. Поскольку корову 4 нужно подоить перед коровой 5, получается, что её нужно подоить второй. Поэтому самое ранее, когда можно подоить корову 1 - позиция 4.