Порядок доїння (Бронза)#10382
У корів Фермера Джона, як завжди зручно пронумерованих , виявилося забагато вільного часу. У результаті вони виробили складну соціальну структуру, пов'язану з порядком, у якому Фермер Джон доїть їх щоранку. Після кількох тижнів спостережень Фермер Джон з'ясував, що ця структура базується на двох ключових властивостях.
По-перше, через соціальну ієрархію корів, деякі корови наполягають на тому, щоб їх доїли раніше за інших корів, залежно від їхнього соціального статусу. Наприклад, якщо корова має найвищий статус, корова — середній статус, а корова — низький статус, то корову потрібно подоїти раніше за корову , а корову — раніше за корову .
По-друге, деякі корови дозволяють доїти себе лише на певній позиції в порядку доїння. Наприклад, корова може наполягати на тому, щоб її подоїли другою.
На щастя, Фермер Джон завжди може подоїти своїх корів у порядку, який задовольняє всі ці умови.
На жаль, корова нещодавно захворіла, тому Фермер Джон хоче подоїти її якомога раніше, щоб вона могла повернутися до хліва та отримати так необхідний їй відпочинок. Допоможіть Фермеру Джону визначити найранішу позицію, яку корова може зайняти в порядку доїння.
Перший рядок містить три цілих числа , та k~(2 \le n \le 100, 1 \le m < n, 1 \le k < n): у Фермера Джона є корів, з них утворюють соціальну ієрархію, а з них вимагають, щоб їх доїли на конкретних позиціях у порядку. Другий рядок містить різних цілих чисел m_i~(1 \le m_i \le n); корови, перелічені в цьому рядку, повинні бути подоєні в тому самому порядку, в якому вони там наведені. Кожен з наступних рядків містить два цілих числа c_i та p_i~(1 \le c_i, p_i \le n), що означає, що корову c_i потрібно подоїти на позиції p_i.
Гарантується, що за цих обмежень існує допустимий порядок доїння.
Виведіть одне ціле число — найранішу позицію, яку корова може зайняти в порядку доїння.
Приклад 1
У цьому прикладі у Фермера Джона є корів, і корова хвора. Він повинен подоїти корову раніше за корову , а корову — раніше за корову . Крім того, корову потрібно подоїти першою, а корову — третьою.
Оскільки корову доять першою, а корову потрібно подоїти перед коровою , яку доять третьою, корову потрібно подоїти другою. Таким чином, найраніша позиція для корови — четверта.